ARC091 問題F: Strange Nim の平易な解説 _1
AtCoderの解説が難しい、、、
AtCoderの過去問にチャレンジ！
AtCoder Reguler Contest (ARC)第91回を解いてみた。
しかしながら、解説が初心者には全く優しくないのであった。。。
そこで頑張って解説を解読しようと決意した。なるべく平易に細かく解説を試みます。
問題F: Strange Nim
問題文
高橋君と青木君は、石取りゲームをしています。最初、山が
個あり、
個目の山には
個の石があり、整数
が定まっています。
高橋君と青木君は、高橋君から始めて、交互に以下の操作を繰り返します。
山を 1 つ選ぶ。
個の石が残っている場合、 1 個以上
個以下の任意の個数の石を
先に操作ができなくなったプレイヤーが負けです。両者最善を尽くしたとき、どちらのプレイヤーが勝つか判定してください。
ただし、
で
以下の最大の整数を表します。
制約
入力はすべて整数である。
解読していく
https://img.atcoder.jp/arc091/editorial.pdf
まず出だしでつまづいた。
各山については独立したゲームとなっているため、各山についてその Grundy 数が求められれば良いです。
Grundy数周りの説明を３行で言うと
- 全てのImpartial gameは、Grundy数を導ければ、そのGrundy数に相当するNimに帰結できる。
- Nimは、（xor演算を応用することで）初期条件からとても簡単に先後どちらの必勝かが分かる。
- よって全てのImpartial gameは、Grundy数を調べることで簡単に解くことができる。
ゲームの勝敗
問題文のようなゲームはImpartial gameと呼ばれ、
- 2人で行うゲームで、決着が着くまで手番を交互にやり取りする。
- 一方が行動できなくなれば、もう一方が勝者となる。
- 有限回の手番で決着がつく。
- プレイヤーはお互い同じ操作をすることができる。
- 偶然に左右されない。
の5つの性質を持つ（Impartial game - Wikipedia)。
このようなゲームにおいては、互いに最善手を取った時に必敗、ないし必勝となる「状態」が存在する。
問題文の例をいくつか考えてみよう。まず、山が1つ、残りの石の数が3つで、k=3の時、先手が1つ石を取ってゲームが終了するので、必勝である。
石を増やして、6個の時も先手が必勝となる。先手は2つ石をとって、残りは4つ。後手は1つしかとれないので、残り3つとなり、先の変化に合流して、先手が必勝となる。
同様に、石の残りの数と、kの値を使うことで、そのゲームの今の状態が、先手必勝なのか先手必敗（後手必勝）なのかを調べることができる。
Grundy数
ここで、Grundy数（Nimberとも言う：Nimber - Wikipedia）を導入することで、このゲームの状態を簡単に表現できるようになる。
数学的に妥当かどうかは置いておいて、その目的は次のようなものだ。
「ゲームの状態を表す数の組 があるとする。この
の要素がGrundy数の要件を満たしていれば、それはImpartial gameの状態を記述できる」
Grundy数は、次のような手順で決定される（Grundy数 - CCS Wiki）。
1.これ以上ゲームが進行(遷移)しない場面のGrundy数を0とする
2.ある場面
でゲームが進行(遷移)するなら次の遷移先)
をすべて列挙する
3.列挙した遷移先
4.未定義の遷移先 A'があるなら、さらに次の遷移先
を列挙しその遷移先 A'のGrundy数を求める
Nim
Nimは、最も単純なImpartial gameであり、Nimの初期値から簡単に必勝か必敗かを調べることができる。 Impartial gameであることは、先の条件と比べてみれば分かる。
複数の山に積まれた石を順番に取り合って、最後の1個をとったプレイヤーが勝ちというゲームです
このページで扱うNimのルールは以下の通りとします
- 2人のプレイヤーで行う
- 1つ以上の山が存在し、それぞれに1つ以上の石が積まれている
- 石を取るプレイヤーは1つの山を選択し、そこから1つ以上の石をとる(全てとってもよい)
- プレイヤーが石を取ったら、石を取るプレイヤーを変更する
- 最後の1個をとったプレイヤーの勝利とする(山に2個以上石があってもよい)
(要するに、山から石を取れなくなったら負けということです)
Nimにおける各山の残りの石の数は、ちょうどGrundy数の条件を満たすことをここで特に述べておく。
石 個の時のGrundy数を
とし、残りの石の数を
として、簡単に証明する。
- 条件1. は、全ての山の石がなくなった時ゲームが終了するため、これを満たしている。つまり
- 条件2~4.は、石が少ない状態から帰納的に考える。
では、遷移先が石0個の時だけなので、遷移先の集合は
。よって
。
- 同様に、
。よって
。
- 同様に、
では、
。よって
。
となる。
Nimの必勝法
NimはImpartial gameなので、必勝法が存在する。しかも、必勝か必敗かを、山の残りの数の（バイナリ表現の）xorを取るだけで簡単に調べることができる。
Nimは「山から石がなくなった状態を相手に押し付けたら勝ち」というゲームと言い換えることが出来ます 山に石が無い状態は各山の石の数のxorが0であることは自明です。よって、以下の2点を証明すればよいことになります
1.各山の石の数のxorが0であるとき、どのようなとり方をしても各山の石の数のxorを0にすることが出来ない
2.各山の石の数のxorが0でない時、各山の石の数のxorを0にするとり方が必ず存在する
補足すると、「各山の石の数のxorが0の状態を相手に押し付け続ければ、いつか石の数が0個の状態が来るから自分が勝つ」ということです
まず、1の証明です 各山の石の数のxorが0であるということは、「各桁に存在する1の数が偶数個である」ということです 山から石を取るという行為は「いずれかの山に相当する数値のビットを少なくとも一つ以上反転させる」ことに等しいです 反転したビットの桁に存在する1の数は必ず奇数になるため必ずxorが0でなくなります したがって、各山の石の数のxorが0であるときどのようなとり方をしても各山の石の数のxorを0にすることは出来ないということになります
次に、2の証明です まず、すべての山のxorをとります。そして、「1である桁の中で最も大きい桁」を探し、その桁が1である山を探します(そのような山は必ず1つ以上あることは自明です) その山から適当に石をとり、「当該桁以下の値がxorの値と同じになるように」石を取ります そのような石の取り方があることは自明です したがって、xorを0にする取り方が必ず存在することになります
Nimへの帰結
Grundy数が求められるなら、全てのImpartial gameはNimに帰結できる（ゲーム理論の定理として知られている：Sprague–Grundy theorem - Wikipedia）。
Nimの必勝法は「山の石の数のxorが0になるようなとり方をする」という戦略でしたね そして、そういう石の取り方が必ず存在することを証明しました
さて、あるゲームの場面がGrundy数の集合S = (a, b, c,・・・)で表現されるとき、その遷移先として
(0, b, c,・・・), (1, b, c,・・・), (2, b, c,・・・), (3, b, c,・・・),・・・(a-1, b, c,・・・),
(a, 0, c,・・・), (a, 1, c,・・・), (a, 2, c,・・・), (a, 3, c,・・・),・・・(a, b-1, c,・・・),
(a, b, 0,・・・), (a, b, 1,・・・), (a, b, 2,・・・), (a, b, 3,・・・),・・・(a, b, c-1,・・・),・・・
の全てが存在していることが保障されているはずです(Grundy数の定義をよく思い出してくださいね。)
これは各山の石の数が(a, b, c,・・・)であるNimにおける石の取り方をすべて網羅していることに等しいです Nimにおける石の取り方をすべて網羅しているということは、「あなたの手番でGrundy数のxorが0でないならGrundy数のxorが0になるような遷移先が存在する」ということになります
今度こそ、本当にNimに帰結できましたね
そもそもNimでは、ゲーム内で出てくる変数がそのままGrundy数となるゲームだった。 その変数を使って、最善の戦略を取った時の勝者を求めることができた。
つまり、ゲーム固有のGrundy数を求めることさえできれば、元のゲームもxorで解ける、と言うことになる。
Grundy数の構成
ここまでで、Grundy数を求めることができれば良いことが分かった（解説に書いてあるそのままだった）。
さて再び解説を読んでいく。
続く
