ゲームの勝ち負けの問題

どうも苦手意識があるので、典型的な解法やテクニックをまとめることにする。
問題を解いたら適宜追加する。未来の自分、よろしく。

動的計画法

dp[盤面] = その盤面からスタートした時に勝つ/負ける
として、勝ち負けが自明な状態（決着がついたときとか）から、貰うDPで計算する感じ。

まねっこ

先に全部取ったら勝ち的なゲームで、後手が先手と同じ行動をとり続けることができれば、最後の1個を後手が取って勝つことができる。
という性質を使って場合分け的に解く感じ。

Nim

各山の個数のxorを取った値を使うと、その値の遷移が勝ち負け状態の遷移と対応している、というやつ。
（どうやって思いついたんだ…）
以下の性質から上手く機能することが何となくわかる。
・xorが0の状態からは正の状態にしか遷移できない
・xorが正の状態からは必ず0の状態に遷移できる
・すべての山が0のときはxorが0で負けの状態

Grandy数

ある盤面のGrandy数＝｛その盤面から遷移できる盤面のGrandy数｝に含まれない最小の非負整数
という値を考えると、これがNimのxorの値と同じように機能する。らしい。

問題例
・ F - Interval Game 2 / Submission #40164729 - AtCoder Beginner Contest 206（Sponsored by Panasonic）