京都大学プログラミングコンテスト 2020 H - Beans on the Grid

解法

豆は自由に選んで操作できるので、定石通り、それぞれの豆に対してグランディ数を求め、最後にxorを取れば良いです。
まず、とりうるグランディ数の値を考えると、遷移先としてあり得るのが{右、左、下}の3パターンが最大です。よって、グランディ数は最大でも3にしかなりません。
そこで、例えば左右の2方向にしか移動できないとしたとき、下方向のグランディ数は4であったと考えても、答えは変わりません。これを利用して、遷移できない部分(皿がないマスやマス目外、一周して同じ方向に進めない場合)の遷移先のグランディ数は4であった、と置くことにします。

豆については、大きく2つのパターンがあります。

ゲーム開始時、もしくは下に移動した直後であり、左右(+下)のどちらも選べる状態
すでに左右どちらかに進んでいて、同じ方向(+下)にしか進めない状態

1のパターンが最終的に欲しいグランディ数になります。下の行から上の行に向かって、順にグランディ数を計算していきます。

今、 $i$ 行目のマス目についてグランディ数を求めるとします。このとき、 $i+1$ 行目については求まっています( $i = H$ であれば、下は全て4です)。
先ほどの2つのパターンのうち、2番目を先に計算します。左に進む場合と右に進む場合は、文字列をリバースすればやることが同じなので、片方についてのみ話します。
$i$ 行目のあるマスにて、左側に進んでいる状態だとします。自分の左隣のマスのグランディ数を0 ~ 4のうち1つ決めると、左と下の遷移先のグランディ数が決まるので、自分自身のグランディ数も決まります。全てのマスについてこれを計算します。
すると、これは区間マージができます。
ある区間について、左端の1マス左隣のグランディ数が $x(0 \leq x \leq 4)$ だったときの、区間の右端のグランディ数 $g_{x}$ 、という情報の持ち方をします。
よくあるダブリングと同様、2つの区間をマージする場合、
マージ後の区間における、左端の左隣が $x$ だったときの、右端のグランディ数は
$rg_{\ lg_{x}}$ となります( $lg_{x}$ で、マージ前の左側の区間に対するグランディ数だとします、 $rg$ も同様)。
また、今いるマス目に皿がなかった場合、 $g_{x} = 4$ です。
こうすることで、今 $(i,j)$ で左に進んでいて、 $(i,k)$ のマスまでしか左に進めない、としたときにおけるグランディ数が、セグメント木を用いることで $O(\log W)$ で計算できるようになりました。具体的には、先ほどの区間マージを繰り返し $[k,j]$ にした後、 $g_{4}$ を見ればよいです。
もし、途中に皿がないマスがあったとしても、その地点でいったんグランディ数が4でリセットされるので正しく計算できます。これにより、皿が無いマスの有無を気にすることなく、好きな地点で左に進み始めた場合のグランディ数が計算できます(とりあえず一周できると仮定して区間マージしてみればよいです)。

では、パターン1のグランディ数を求めます。
下方向の遷移先のグランディ数はすでに求まっています。
左に進んだ場合、遷移先のグランディ数はパターン2のグランディ数になります。
よって、 $(i,j)$ から左に進むとしたとき、 $(i,j-W+1)$ までしか左に進めない場合における、 $(i,j-1)$ のグランディ数を計算すればよいです。
右も同様です。
3つの遷移先のグランディ数がわかったので、自分自身のグランディ数は定義通り計算できます。
これで、欲しかった情報が手に入ったため、あとはxorを取って0かどうか判定すれば答えがわかります。
実装は、 $W,1$ の行き来をスムーズにするために、それぞれの行における文字列を2回繰り返せばより実装が楽になります。