ARC151 C - 01 Game (600)
数字を色に置き換えて考えている
最初の考察
あるところに置くとそれ以降はその左右で干渉することがないので独立に考えられそう
先手が勝てるところと負けるところの数によって全体の勝敗が決まりそう
少ない数で実際に試してみると同色で囲まれている場合は勝ち、違う色なら負けになりそう
一個も色がない場合
奇数の場合真ん中において勝ち
偶数の場合に対称の位置に逆の色を置かれて負け
最終的な考察
Grundy数で考えた方がよさそう
intではなくlong longが必要なことに注意
同色の間は全て1、違う色の間は全て0
同色の間で置く場所が無いパターンは除く
端の片方だけ色がある場合、塗られていない長さがそのままGrundy数になる
Nimと同様に区間毎にXORを取り、0にならなければ先手の勝ちでなったら後手の勝ち
石のある位置を端から見ていくことになるので$ \mathcal{O}(M \log M)