Sprague-Grundy Theorem すげー

echizenライブラリを見て見つけたもの。さすがoxy神。

Sprague-Grundy theorem - Wikipedia, the free encyclopedia

これはすごい。久々に感動した。

簡単に解説すると、この定理は、打つ手がなくなったときに負けとなるような二人零和有限確定完全情報ゲームの局面はすべてNimというゲームの局面と同型であるというもの。Nimには必勝法が知られているので、これと組み合わせることでゲームの先手必勝・後手必勝を判定するアルゴリズムを作ることができる。
ちなみにNimというゲームは次のようなゲーム。テーブルの上にk塊の石の山があり、それぞれ n1,n2,...,nk 個の石からなっている。これから二人が交互に、それぞれ一つの山から任意の数(ただし1個以上)の石を取っていく。最後の石を取った人が勝ち。
特に、Nimはそれ自体、複数の山からなる局面と一つの山からなる局面が同型になっている(どういう意味で同型なのかはWikipediaの解説を見てください)。なので、複数のゲームがそれぞれ独立かつ同時に行われる場合、その解析にこの定理が大活躍するのです。すなわち、同型な一つの山しかないNimに還元したとき、その山の大きさが0なら後手必勝、1以上なら先手必勝となる。という感じ。

これでずっと謎だった PKU2311 Cutting Game を解くことができた。考えた人はすごいなあ。