石取りゲーム(Nim)
石の山から交互に石を取っていくゲーム。三山崩し、などとも呼ばれる。
基本ルール
必勝法
山に残る石の数のリストを $[a_1,a_2,...,a_N]$ とする
2進数表現の各桁の排他的論理和 $X$ を計算する
-
$X = a_1 \hat{} a_2 \hat{} ... \hat{} a_N$
（例）$[5, 9, 11]$ ⇒ 2進数表現で $[101, 1001, 1011]$ ⇒ $0101 \hat{} 1001 \hat{} 1011 = 0111$ となり、$X = 111$
$X=0$ の状態を「必勝形」と呼ぶ
初期状態で必勝形なら後手必勝、それ以外なら先手必勝
ゲームの途中では、常に「自分が取った後の状態」が必勝形になるように取る
最終状態（石が無くなった状態）は必勝形であり、自分が取った後に石が無くなる＝自分が最後の石を取ったので勝ちである。
自分が取った後を必勝形にし続けると、いつかは最終状態、つまり最後の石を取れることになる。
証明
必勝形からどのように取ろうとも、必勝形のままにはできない
必勝形でない状態から、必勝形にする取り方が必ず1つ以上存在する
1の証明
ある山 $i$ から取るとき、自分以外の山の排他的論理和（$X \hat{} a_i$）は変わらない
よって、操作後に必勝形にできる石の数を $a_i'$ として、$a_i'=X \hat{} a_i$
しかし、操作前が $X=0$ だと $a_i'=a_i$ となるが、少なくとも1つは石を取らないといけないので、不可能
2の証明
実際にできる方法を示す。
X で最も左に1が立っている桁を d 桁目とする。
d
X 0001100101
d 桁目に1が立っている ai は必ず存在する（存在するからXでも立ってるのだ）
どれでもいいので1つ選ぶ
ai 1001001100
Xとaiのxorを計算する。これが操作後の ai' となるように、ai から石を取る
X^ai 1000101001
~~~|~~~~~~
1 2 3
このとき、元の ai から、
1の範囲は変わらない
2の箇所（d桁目）は必ず 1→0 に変化する
3の範囲はいろいろ
変化する最も大きい桁が $d$ 桁目であり、それが1→0に減少しているので、操作後の $a_i'$ は必ず元の $a_i$ より小さい。
逆型ルール
必勝法
最初から石が1個の山しか無い場合、山の数 $N$ が奇数なら後手、偶数なら先手必勝となる。
石が2個以上の山が存在する場合を考える。
結論から言うと、逆型ルールでも必勝形を維持し続ける方が必勝である。
「石が2個以上残る山」の数がポイント
必勝の方は、自分の手番の時、
石が2個以上残る山が2つ以上なら、「最後の石を取った方が勝ち」ルールと同様、必勝形になるように取る
石が2個以上残る山が1つの時、
自分が受け取る時、石が2個以上残る山が1個の状態になるタイミングが必ずある
3の証明
「石が2個以上残る山」をTと呼ぶことにする
自分の手番でTが2個以上で受け取った時、必勝形を維持するように取れば、取った後もTは2個以上残る
Tが2個以上の状態から一手で0個の状態にはできない
石の個数は一様に減っていくので、どこかでTが1個の状態が必ず発生する
NimK ルール
選べる山の数について、一般化されたNim。NimKと呼ばれるらしい。
必勝法
各山の石の個数を $A_i$ とし、$A_i$ を2進数表記する。bitごとに、全ての山について足し合わせる。
A1 1 0 1 1 0
A2 0 1 1 1 0
A3 1 0 0 1 0
--------------
2 1 2 3 0
足し合わせた各桁について、$K+1$ で割った余りを取る。
これが全ての桁について $0$ なら後手必勝、$0$ でない桁があれば先手必勝。
つまり、
NimK の逆型ルール
必勝判定は変わらず。（最初から石が1個の山しかないなどのコーナーケースを除く）
途中までは通常と同じく、全ての桁のmod K+1 を0にしつつゲームを進める。
必勝側は、石が2個以上残る山の数が $K$ 個以下で渡された瞬間、「石が1個だけ残る山の個数を、$K+1$ で割ったときに1余るように残して取る」とよい。
Grundy数による一般化
このように、お互い交互に操作して状態を変化させ、それ以上操作できない状態になったら勝ちというゲームにおいて
先手・後手のどちらが必勝かは、Grundy数（ニム数、Nimber）というものを求めることで判定できる場合がある。
Grundy数が使えるのは、不偏ゲームに限られる。
Grundy数とは、以下によって求められる。
このGrundy数を各部分状態について求め、xorが0なら後手必勝、それ以外なら先手必勝となる。
石取りゲームに戻って当てはめると、
石の山が $N$ 個ある＝全体の状態
石の山1つ＝部分状態
山に残る石の数＝その山のGrundy数
石が0個ならもう操作できない（最終状態）のでGrundy数は0
石が1個なら、0個にできるので、Grundy数は1
石が $a_i$ 個なら、0から $a_i-1$ 個の全ての状態に遷移できるので、Grundy数は $a_i$
ちゃんと当てはまっている。
Grundy数の適用例
取れる石の上限が設定
例えば、「1つの山からは一度に3個までしか取れない」ルールが加わったとする。
すると石山のgrundy数は、
となる。要は4で割った余りだね。
部分状態を分割
「山から石を取るのでは無く、2つの山に分ける。全ての山を石1個にした方が勝ち」というルールになったとする。
状態が分裂して増えていくタイプも、分裂した各状態のxorで考える。
ある状態を状態 A,B,C に分割するような操作があったとして、遷移先のGrundy数は $G_A \hat{} G_B \hat{} G_C$ として扱えばよい（ただし、状態AのGrundy数を $G_A$ と表す）。
1個の山は最終状態なので $G_1=0$
2個の山は(1個,1個)に遷移できる
3個の山は(1個,2個)に遷移できる
4個の山は(1個,3個)または(2個,2個)に遷移できる。
(1個,3個)のとき、$G_1 \hat{} G_3 = 0 \hat{} 0 = 0$
(2個,2個)のとき、$G_2 \hat{} G_2 = 1 \hat{} 1 = 0$
「0」の状態にのみ遷移できるので、$G_4=1$
5個の山は(1個,4個)(2個,3個)に遷移できる。
(1個,4個)のとき、$G_1 \hat{} G_4 = 0 \hat{} 1 = 1$
(2個,3個)のとき、$G_2 \hat{} G_3 = 1 \hat{} 0 = 1$
「1」の状態にのみ遷移できるので、$G_5=0$
まぁ、蓋を開けてみればつまらないが、偶数なら1、奇数なら0となる。
取れる石の上限と下限が設定
競技プログラミングに出るようなNimの問題は、解けるようにできているので、
実際に実験をすると意外と単純な性質が見えることがある。
解法
山に残る石の数ごとに、取れる石の上限と下限が設定
「山に残る石が $i$ 個のときは $L_i～R_i$ 個の石を取れる」という $L_1,R_1,L_2,R_2,...$ が決まっている
山にある石の個数は、たかだか $10^5$ 程度
やや高難度。
規則的な遷移にならないgrundy数は、遷移先全てのgrundy数を調べてそのMexを計算する必要があり、計算量がかさみやすい。
この問題では、計算量を現実的な程度に抑えるのに工夫が必要となる。
解法
$i$ 個の状態からは $(i-R_i)～(i-L_i)$ 個の状態に遷移できる。
この区間のgrundy数のMexが、$i$ 個の場合のgrundy数になる。
i 0 1 2 3 4 5 6 7
Li - 1 1 1 1 1 2 3
Ri - 1 2 3 1 2 5 5
遷移できるi - 0~0 0~1 0~2 3~3 3~4 1~4 2~4
grundy数 0 1 2 3 0 1 4 1
$i$ 個の状態のgrundy数を求めるのには、愚直には、$R_i-L_i+1$ 個の遷移先全てのgrundy数を調べる必要がある。
つまり、最大の山の石数を $A_{\max}$ とすると、そこまでのgrundy数を求めるのに、$L_i,R_i$ の与えられ方にもよるが $O(A_{\max}^2)$ かかる。
石の数が大きくなってくると非常に時間がかかってしまう。
求めたいのがMinやMaxなら、セグメント木を用いて区間のそれを高速に求めることができるが、Mexはできない。
（$\{0,1,3\}$ のMexは $2$, $\{2,4,5\}$ のMexは $0$、この2つの和集合のMexは $6$ となる。
しかし $2$ と $0$ という情報だけから $6$ を導き出すことはできないため、元の集合そのものの情報が必要になり、計算量が改善しない。）
ここでは、「最も直近に出てきた、grundy数が $g$ となる箇所 $i$ はどこか？」を、$g$ をindexとしてMinセグメント木で管理する。
$i$ の小さい方から順に処理していく。
$i$ のgrundy数が $m+1$ となるとなるということは、$i-L_i$ の更新が終了したタイミングで、以下の2つが満たされている状態と言い換えられる。
そのような $m$ は、Minセグメント木で二分探索することで $O(\log{A_{\max}})$ で求められる。
$i$ の小さい方から以下を処理していく
$i$ まで到達した段階で、$i$ のgrundy数 $g$ は求まっている
Minセグメント木の、indexが $g$ の項を $i$ に更新する
$i=j-L_j$ である $j$ について、二分探索でgrundy数を求める
としていくと、全体で $O(A_{\max}\log{A_{\max}})$ で求められる。