Nim, Grundy数 - Githubissues

tipstar0125 / atcoder

atcoder

6 stars 0 forks source link

Nim, Grundy数 #27

Open tipstar0125 opened 7 months ago

tipstar0125 commented 7 months ago

Nim, Grundy数を考える前に、以下で解けないか考える。

まず初手で「必勝状態」に持っていって、それ以降は相手の行動の真似をしたり打ち消したりするような操作を取り続けることで必ず勝てる

参考：

tipstar0125 commented 7 months ago

Nim

【ルール】

石が何個か積まれた山が N個ある
2人で交互に石を取り合う
石は、一度に1つの山からしか取れない。同じ山からなら1個以上何個取ってもよい
最後に石を取った方が勝ち

【判定方法】

山が一つのとき：先手必勝
山が二つで、コインが同じ枚数：後手必勝
- 後手が先手のマネをすれば勝てる
- 実は同じコインの枚数が、二つだけではなく、偶数個あれば、後手必勝(★重要)
XOR sumが0ではないとき先手必勝

tipstar0125 commented 7 months ago

grundy数

最終状態のgrundy数を0とする
ある状態のgrundy数は、そこから1手で遷移できる全ての状態のgrundy数のMex
普通のNimの場合は、1個以上何個取ってもよいので、遷移先は、山の数より1小さい値以下なので、grundy数は山の数そのもの

grundy数の求め方

ゲームは後ろから
最終状態のgrundy数を0とする
1, 2, ...と順番に遷移できる全ての状態のgrundy数のMexを求める
遷移できる状態がない場合はgrundy数は0（最終状態と堂々）

tipstar0125 commented 7 months ago

Nimに個数制限Kが加わったとき
- Kが山の最大以上であれば、普通のNimと同じ
- 上記以外であれば、山の数をK+1で割ったあまりがgrundy数
Nimに取れる数がX or Yと制約が加わったとき：https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_dg
- grundy数の求め方に従って、計算すると周期性が現れる
- 前の状態を一定の規則に従って、計算するので、それはそう

tipstar0125 commented 7 months ago

XOR sumが計算制約上簡単に求められない場合：https://atcoder.jp/contests/arc168/tasks/arc168_b

普通のNimでXOR sumが非0ならば先手必勝
普通のNimでXOR sumが0の場合
- Ai mod (k+1)が非0になる最大のkを求める。ただし、愚直にやるとTLE
- 同じ個数の山はXOR sumすると互いに打消しあう。これをして、全てなくなれば、XOR sumは0になるので後手必勝
- 上記の通り打消しあうと、残りは奇数個の山だけになる。この状態で、山の最大をMとする
  - k>=Mのときは、普通のNimのXOR sumと同じで、XOR sumは0となるので、M-1以下について考える
  - k=MのときのXOR sumが0なので、k=M-1にしたとき、最大の山のmod (k+1)は0になる。k=Mのときは、最大の山MをXORすると0になるので、直前までのXOR sumはMである。よって、k=M-1のときはXOR sumは非0(M)になり、答えはM-1。