SRM637Div1Medium
問題
高さ2、幅Wのボードが与えられる。各マスは黒か白である。ひとつの白いマスを選択し、それを黒に変える。ただし、左側から右側に白いマスだけで行けるルートは残さないといけない。この操作を2人で交互に行う。操作ができなくなった方を負けとする時、勝者がどちらになるかを求める。
解法
Grundy数を用いることでNimに帰着することができる。
ある列を選択した時に、上か下のマスが黒である場合はその列の白マスを黒に変えることはできない。白マスだけでできているボードを取り出し、それに対してGrundy数を求める。この時の左右の状態に注目する必要がある。白いボードの左にある列の上のマスが黒である場合は、白いボード内の最も左にある列では上の白マスしか黒に変えられない。得られた白いボード内の端ではないある列を選ぶ。その列の上を黒マスにした時の左のGrundy数と右のGrundy数をXORする。同様のことを列の下のマスにも行う。これを全部の列に行うことで、このボードのGrundy数が求められるようになる。
計算量
