けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

隣の山に石を渡していく Nim (staircase nim)

Nim けんちょん自作問題 ゲーム 気付き系 条件の言い換え テーマ解説記事 駒(コマ)や石やコインを扱う問題 一次元グリッド Staircase Nim

ふと TL に出してみた。絶対既出だと思ったから流したけど、どこかにあるかな...？？？

アイディア自体は

  • SRM 309 DIV1 Hard StoneGameStrategist
  • POJ 1704 Georgia and Bob (蟻本の例題)

と同じものだったりする。むしろ問題に対してある種の同型変換を施すと、3 問ともまったく同じ問題であることが示せたりする！！！！！

あと、staircase nim という名前があるらしい。

問題概要

n 個の石の山が左から順に一列に並んでおり、それぞれ a_i 個の石を含んでいる。右端の山の右横には石置き場があり、最終的に全ての石を石置き場に移動させることを目指す (先にその状態にした方が勝ち)。

先手と後手は交互に空でない石の山を一つ選び、そこから1個以上の石を取ってそれを右隣の山に移動させる。右端の山から石を取った場合は、それを石置き場に移動させる。お互いが最善を尽くしたとき、先手後手どちらが勝つでしょうか？

制約

  • 1 \le n \le 10^{6}
  • 1 \le a_i \le 10^{9}

解法

まず、(5, 0, 6, 0, 100, 0, 4, 0, 7, 0) みたいな「右から奇数番目がすべて 0」という盤面は既に必敗盤面になっていることに注意する。何故なら例えばこの盤面の石 100 個の山から 9 個とって

(5, 0, 6, 0, 100, 0, 4, 0, 7, 0) -> (5, 0, 6, 0, 91, 9, 4, 0, 7, 0)

としたとき、相手は

(5, 0, 6, 0, 91, 9, 4, 0, 7, 0) -> (5, 0, 6, 0, 91, 0, 13, 0, 7, 0)

としてしまえばよい。こうして同じ形に持ち込むことができる。このことから、「右から奇数番目の個数」はどうでもよくて、

  • a_{n}, a_{n-2}, a_{n-4}, \dots についての Nim なんじゃないか...？

という着想が浮かぶ。そのことを示してみる。

証明

以下の 3 つを示せば良い:

  1. a_{n} ^ a_{n-2} ^ a_{n-4} ^ \dots = 0 のとき、次にどのような手を打っても、その条件が崩れる
  2. a_{n} ^ a_{n-2} ^ a_{n-4} ^ \dots \neq 0 のとき、上手く手を打つことで a_{n} ^ a_{n-2} ^ a_{n-4} ^ \dots = 0 の状態にできる
  3. 操作は有限回数で必ず終了し、終局状態は a_{n} ^ a_{n-2} ^ a_{n-4} ^ \dots = 0 の状態である

まず、右から奇数番目の山のみに着目してみたとき、

  • 山を 1 つ選んで石の個数を任意に減らせる (右隣の山、もしくは石置き場に石を任意個数移す操作に対応)

という通常の Nim に対し、

  • その山の石の個数を少しだけ増やすこともできる (左隣の山から石が持ち込まれることに対応)

という操作もつけ加わったものだと思うことができる。実はこの程度の操作変更では Nim はビクともしない！！！

1. について

石の個数が増える操作が加わっても、操作を行うと必ず

  • a_{n} ^ a_{n-2} ^ a_{n-4} ^ \dots = 0

が崩れることは自明である。簡単のため、 a ^ b ^ c = 0 が成り立っているときに c を d に変更するものとする。このときまず XOR の性質から

a ^ b = c

が成り立っているため、

a ^ b ^ d = c ^ d

となる。 c = d でない限り、 a ^ b ^ d = 0 とはならないことがわかる。

2. について

これについては「石の個数が増える」という操作の追加は何も意味を持たない。従来の「石の個数を任意に減らせる」という操作だけで

  • a_{n} ^ a_{n-2} ^ a_{n-4} ^ \dots \neq 0 の状態から a_{n} ^ a_{n-2} ^ a_{n-4} ^ \dots = 0 の状態にすること

が実現できるのは、通常の Nim と同じである。

3. について

通常の Nim に「石の個数を増やす」操作を追加したものも実質 Nim と同じだと言ったが、厳密にはダメ。何故ならその場合、ゲームを無限に続けることができてしまうから。。。

でも、この問題のゲームの場合は、

  • a_{n} + 2 × a_{n-1} + 3 × a_{n-2} + \dots

の値が常に単調減少なので有限停止性が保証できる。そして終局時の各山の石の個数は (0, 0, \dots, 0) であり、これは a_{n} ^ a_{n-2} ^ a_{n-4} ^ \dots = 0 の状態である。

まとめ

以上より、

  • a_{n} ^ a_{n-2} ^ a_{n-4} ^ \dots = 0 ならば後手必勝
  • a_{n} ^ a_{n-2} ^ a_{n-4} ^ \dots \neq 0 ならば先手必勝

であることが導かれた。