プログラミングコンテストチャレンジブック 4-2 その2
4-2 の続きからです。
- Georgia And Bob - 一列のマスに並んだ駒を一方向に詰めるように動かしていって動かせなくなったほうが負け
- 駒を2つずつペア(山に相当)にして Nim と同じゲームに帰着できる
- コインのゲーム2 - コインの山から交互に取っていって最後に取ったら勝ち。ただし一度に取れるコインの個数は決まった数のいずれかでないといけない
「多くのゲームは Grundy 数を求めることができます」とあるけれど、Grundy 数が適用できるかどうかの判断方法が書かれていないような。
- Cutting Game - 格子に区切られた長方形の紙を交互に切っていって最初に1x1の格子を切り出したほうが勝ち
- これも Grundy 数を求めることができる。紙を切って2つに分かれた時に g1 XOR g2 でまとめて表現できる