CADDi 2018 D - Harlequin (500)

• 問題

解法

公式動画&解説で基本的にわかるので個人的な備忘録にとどめておく.

ゲームの問題の基本的な戦略として,手で書いて実験をする.
N個の数のケースで実験すると1回の遷移が O(2^N) になるので, N=2で実験する.
公式解説のようなグラフを書いて実験をすると良い.
これは結構定番で ARC 072 D - Alice&Brown - 主食は米 とかもこれを使って解ける.

2個で大体のパターンがわかると一般化できそうだという気がしてくる.
この際に用いるのが相手がどのような手をとっても同じ状態に戻せるということで,
この問題であれば 全て偶数/それ以外 の状態に全ての状態をまとめることができ,
全て偶数という状態が最終的に相手の負けになるので,解説の答えが出る.

メモ

N=2 の状態で実験をしてグラフを書くのはマストな気がする.
最初からNが大きい状態で考えてしまって解けなかった.