きろく

特筆すべき記録のまとめ

CADDi 2018:D - Harlequin

問題

atcoder.jp

解法

答えは「全ての色の個数が偶数であれば "second",そうでなければ "first".」になる.

相手に全ての色の個数を偶数で渡すことが出来れば,相手が任意の色の個数を奇数にしてきたとしても,こちら側で奇数にされたところを偶数にすることが出来るので,相手は一度全ての色の個数を偶数で渡されたらゲーム終了までずっと偶数個のままになる.そうなると,相手は当然負ける.なので,相手に全ての色の個数が偶数である状況で渡せるかどうかを判定すればよい.これは,初期状態で1つ以上でも奇数個の色があれば,その色の数を偶数にして相手に渡すだけなので自分は勝てるが,初期状態で全ての色で偶数個だった場合,取らないという選択肢は無いので相手にどれかの色の種類を奇数個で渡すことになってしまう.よって,最初の答えは正しい(多分).O(N).

解答

atcoder.jp

一発 AC 出来てよかったけれど,証明がガバガバな感じがする...

f:id:babcs2035:20181222231526p:plain