C: 茶碗と豆 - AtCoder Regular Contest 038
位置iにある石を移動させるゲームを行う。位置iの石は左に1からC[i]の範囲で好きなだけ動かすことができる位置0にある石はそれ以上移動させることができない。先攻と後攻どちらが勝つか。
まずは位置iに石が1個ある時のGrundy数を愚直に計算する。位置0にある時、先攻の負けなのでGrundy数は0。あとは左から順にGrundy数を計算する。例えばgrundy数が{0, 1, 2} のとき、C[3]=2 ならば、一手勧めたときにあり得るGrundy数集合は{1, 2} であるから、この集合に含まれない最小の非負整数なので結局Grundy数は0になる。
さて、これを愚直に計算すると、石の数が1個の時Grundy数の1回の計算にO(N)の計算量が必要になる。そこで、インデックスがGrundy数を表し、そのGrundy数が最後に現れた石の位置を値に持つようなRMQを考える。すると、例えば[0, x)のminがi - C[i] 以上である時、すなわちGrundy数が [0, x) の範囲において、そのGrundy数が最後に現れたIndexが全てi - C[i] 以上である時、iにある石はいずれも [0, x)の範囲のGunrdy数を取ることが可能である。そこで、このようなxの上限を二分探索する。ただし、まだ1回も現れてないGrundy数の値は-1とする。すると、xがGrundy数になる。
このRMQをSegment Tree等で実装すると一回のGrundy数の計算がO(logN)になり、全体の計算量はO(N logN)になりまにあう。
