Yukicoder 524 コイン
N(0<N<2^32)枚のお皿に1個、2個、…、N個の石が入ったNIMを行う。先手の勝ち負けを判定せよ。
Editorial読むと単なる実験ゲーでmod4 = 3を出すだけ。
ここでは自分で解いた時の考察を残す。
NIMなのでGrundy数を計算する。Grundy数は1 xor 2 xor 3 xor ... xor Nであり、これが0なら先手の負け、それ以外は勝ちである。
ただし、Nが大きいのでO(N)では間に合わない。そのため各bitごとにxorを計算し、1になる桁があった時点で勝ち判定を返す。
1桁目は1 0 1 0 の繰り返しなので、N mod 4が1または2の時1なので、勝ち確定。それ以外のときは2桁目へ進む。
2桁目は0 1 1 0 0 1 1 の繰り返しなので同様に判定する。これを最上位の桁まで行う。すべての桁で0であれば負け確定。
