競プロにおけるNim、Grundy数とNimK

この記事は、「競プロ!!」競技プログラミング Advent Calendar 2017 21日目の記事です。
昨日は DEGwer さんの「数え上げテクニック集」でした。まだ全部読んでないけど凄かったです。
こっちでも同時に競プロのアドベントカレンダーが進められています。

Nim,grundy数がわかっていると、盤面を共有して二人で対戦し、勝敗が必ず決するタイプのゲーム問題がわりとサクッと解けます。
最近では 5日前、2017/12/16 の Atcoder Regular Contest 087 E で Grundy数の問題が出ました。

この記事の本題はNimの拡張されたゲーム、NimKの話です。
導入として、Nimとかgrundy数を知らないひとにもわかるようにスライドを作成しました。
絵を描くだけのつもりだったのにスライドになってしまいました。
適当すぎてわからん！と思うひともいるかもしてないので参考リンクも貼りました。
それらのページを見てから戻ってきてくれるとうれしいです。

・参考になる記事

augusuto04さん、pekempeyさんの記事が特にわかりやすいです。書いてあるゲームを実際にやりながら考えてみてください。

(1) Grundy数の概要が分かる記事

Grundy数その１ - へなちょここーだー
 http://pekempey.hatenablog.com/entry/2016/01/16/190208

(2) Nim

Grundy数その2 - へなちょここーだー

・他の参考記事
不偏ゲームがNIMに帰着する証明 - SSSSLIDE
グランディ数 - zukky162のブログ
 grundy number - EAGLE 雑記
 grundy数を習得したかった - nanikakaのAOJ航海日誌

・練習に良さそう

最初のリンクは超絶おすすめ、これだけ解けるようになれば優しい問題は大体解ける
Hacker Rank 5 days of game theory (15問あるけど最後のやつ以外は基本だけで解ける)
- 解説はこの記事が参考になると思います。

yukicoderのNimのタグ
 yukicoderのGrundy数のタグ
 競技プログラミングにおけるゲーム問題まとめ [Nim,Grundy数,後退解析,ミニマックス法] - はまやんはまやんはまやん
 競技プログラミングの不偏ゲーム(Nim, grundy数にまつわる)問題集 - かっさのなにか

本題

・NimK について

NimKとは、一般に知られているNimの拡張です。
プレイヤーは二人のまま、打てる手が変化します。

プレイヤーは自分のターンでK個の山を選択し、それぞれの山に対して好きな数だけ石を取ることができる。

各山に対して石を取ることのできる数が制限される場合など、いろいろな制約がつくパターンもあるようですが、ここではどれだけでも取れるとします。
問題っぽくすると次の文章になります。

$N$ 山の石を取るゲームををAlice,Bobが行う。このゲームではすべての石の中で最後の石を取った人が勝ちです。(石を取れなくなった人の負け)
各山には $pile[i]$ 個の石が積まれている。プレイヤーは各自分のターンに $K$ 個までの山を選択し、各山について石を1つ以上なら何個でも取ることができる。
2人が最適な石の取りかたをする時、Aliceが先攻ならば勝つことができるか？
制約: $1≤N≤10^5$ , $1≤pile[i]≤10^9$ , $1≤K≤10^5$

f:id:Yang33-kassa:20171221201155p:plain

実際にシュミレーションをして、grundy数を出すことは可能ですが、KやNが大きいときは状態数がやばいので厳しさがあります。

先に必勝法の判定は何かを書いておきます。
各山にある石の数を2進数で表したとき、これを
$pile(i)= 2^x*bin(i,x) + 2^{x-1}*bin(i,x-1) + 2^{x-2}*bin(i,x-2) + ... + 2^2*bin(i,2) + 2^1*bin(i,1) + 2^0*bin(i,0)$
となるように $bin(i,x)$ を作成します。
次に $N$ 個の $pile(i)$ についてこれを作成し、 $bin(i,x)$ を同じxについて次のように足し合わせます。
$digitsum(x)$ = $( \sum_{i=0}^{N-1} bin(i,x) )$ $mod (K+1)$
このとき、 $digitsum(x)%(K+1)$ が 0 でなくなるような $x$ が存在する場合には必勝です。(値を復元するとこれがgrundy数になっている)
f:id:Yang33-kassa:20171221202605p:plain

通常のNimでもこれが成り立っています。
Xor (排他的論理和)でgrundy数を求めるものもありますが、あれは2進数の各桁同士の和を $mod$ $2$ で計算した値と一致します。どちらの計算も2進数でみると各桁の数字は1の出現回数の偶奇で決まるためです。

この前NimKについて先輩と話したところ、「本当にいつものNimと一緒で必ず勝ちの目を維持できるんですか？」といわれてウウッとなり、本当に正しいのかを考えてみて怪しいのですが少し証明をしてみました。エレガントではないし、厳密ではないかもしれないので間違っていたら教えてください。証明とかイヤ！という人はとばしてください。

▶ひらく

考えたこと(ガバ証明)
ゲームの終端を $P$ $position$ とする。これは負けの状態です。 ( $\forall{x}$ $digitsum(x) = 0$ )
今 $P$ $position$ から始まって $P$ $position$ あるいは $not$ $P$ $position$ への移動が存在するかを考えます。

これを発見するためには、 $P$ $position$ からの任意の移動を行ってみます。
これは少なくとも1つの $x$ について、 $digitsum(x)$ の値を変更することになります。
$P$ $position$ から移動し,各桁 $K$ までしか値を減らすことはできないため、値を減少させながら0でない $digitsum(x)$ を一つも残さない様な手は存在しません。したがって $P$ $position$ からの移動は $not$ $P$ $position$ への移動となります。
次に、 $not$ $P$ $position$ の状態で $P$ $position$ に移動できるかを考えます。
$not$ $P$ $position$ ということは、少なくとも一つの $x$ について、 $digitsum(x)$ は $1≤digitsum(x)≤K$ となっています。
もし $digitsum(x)$ $\neq$ $0$ であるような $x$ について、 $pile(y) =0,$ ( $y$ は $x$ の候補に入らないもの)のまま、これを $digitsum(x) = 0$ にできる $pile(i)$ ( $0≤ i ＜N$ ) の残り方が存在すれば $not$ $P$ $position$ から $P$ $position$ への移動が存在します。
これで、少なくとも $P$ $position$ ー＞ $P$ $position$ への移動はないことがわかりました。
また、先のような手が存在するとすると、これはいつものNimのようなゲームと同様に、適切な手を選択すれば必ずゲームの開始前に先手必勝か後手必勝かを判定することができます。

そのような手が存在しないと意味が無いので、
次にそのような手が存在するかを考えます。

$not$ $P$ $position$ -> $P$ $position$ となる手が必ず存在することの証明
ここでは必ず $not$ $P$ $position$ から、 $P$ $position$ となるような手が存在することを示すことで証明とします。

$M = \sum_{i=0}^{N-1} ( 2^x * digitsum(x) )$ とします。今、 $M \neq 0$ となっています。またこのとき、 $digitsum(x)$ = $digitsum(x)$ $% (K+1)$ としておきます。すると $digitsum(x)$ は $K+1$ 進数となっています。
$M$ の $0$ でない最上位の桁の数を $digitsum(L)$ とします。(下の桁から $L+1$ 番目)すると、 $pile(i)$ の2進数に展開したものの中に、 $2^L$ の値について少なくとも $digitsum(L)$ 個の $1$ が存在します。(実際には非負整数を $n$ として $digitsum(x)$ $+ n(K+1)$ 個だけ存在する可能性はある)
あと、あとで使うのでこの値を $digitsum(L)copy$ とか適当な名前をつけます。
これにあてはまる $pile(i)$ を減らす候補とします。
まず、 $digitsum(L)$ を0にするためにこれらの候補の $pile(i)$ の $2^L$ につく数を1から0にして、更にそれより下の桁をすべて $1$ となるように変更します。(最上位の桁を触るので下の桁は自由な値に設定できる)
この操作によって $digitsum(L)$ は0になりますが、 $digitsum(l)$ ( $l ,0≤ l \leq L-1$ ) の値は変化します。

次に、 $M' = \sum_{i=0}^{N-1} ( 2^x * digitsum(x) )$ とします。
$M'$ の $0$ でない最上位の桁の数を $digitsum(L')$ とします。(下の桁から $L' + 1$ 番目)
先の操作から、 $M$ の一番大きい桁は $0$ にしたので、 $L ＞ L'$ となっています。また、 $M$ -> $M'$ への変更で選んだ $pile(i)$ の2進数展開した $L' + 1$ 桁目は全て $1$ になっています。
なんか2つ状態があるっぽいのでこれを場合分けします。
(ⅰ) $digitsum(L)copy$ $≧$ $digitsum(L')$
この場合は、前の操作で選択した $pile(i)$ のうち $K$ 個以下の $pile(i)$ を選択することで、 $digitsum(L')$ を $0$ にできる。

(ⅱ) $digitsum(L)copy$ $＜$ $digitsum(L')$
この場合は、前の操作で選択した $pile(i)$ の $L' + 1$ 桁目の値を $0$ にすると、 $digitsum(L')$ は前の $digitsum(L')$ - $digitsum(L)copy$ となっています。(操作した分を引いただけ)
さらに残った選択候補のうち、 $L' + 1$ 桁目が $1$ となっているものを $digitsum(L')$ - $digitsum(L)copy$ 個だけ選択し、今までと同じ操作を行う。

この操作によって、変更された $digitsum(L)$ $=$ $0$ , $digitsum(L')$ $=$ $0$ となります。
これを繰り返すことによって最大K個の数値を変更させることで、 $\forall{x}$ $digitsum(x) = 0$ を達成することができます。

はてなブログの $tex$ 記法がめんどくさすぎる。疲れました。

というわけで、存在します。

1つの山しか選択できない Nim と同様に手番を常に勝ち→負けへと動かすことができます。

コードを見たほうがはやい！みたいな人もいるはずなのでC++で先の問題のコードを書きました。上に書いたとおりに書いただけなので実際にはbin[i][x]とかは使わずに書けます。

void Nimk(int N, int K, vector<int>& pile) {
	vector< vector<int> > bin(N, vector<int>(30, 0)); // 2次元配列

	for (int i = 0; i < N; i++) { //pile[i]について、2進数に展開する
		int twopow = 1; // 2のべき乗
		for (int x = 0; x < 30; x++) {
			if (twopow & pile[i])// 2^xにくっつく数は0か1か
				bin[i][x] = 1;
			else
				bin[i][x] = 0;
			twopow = twopow * 2;
		}
	}

	vector<int> digitsum(N, 0); // 桁ごとの和

	for (int x = 0; x < 30; x++) {// 桁xについて
		for (int i = 0; i < N; i++) {
			digitsum[x] = digitsum[x] + bin[i][x];
		}
	}

	int win = 0; // 負けを0、勝ちを1とする
	for (int x = 0; x < 30; x++) {
		if (digitsum[x] % (K + 1) != 0) {
			// 桁の値が0ではないときは勝ちのポジション、grundy数が0でないことが確定する
			win = 1;
		}
	}

	if (win == 1) { // 先手の勝ち
		cout << "Alice" << endl;
	}
	else { // 先手の負け
		cout << "Bob" << endl;
	}

}

実際に解いてみましょう！

蟻本4-2節の練習問題にもある、 POJ2315 は問題文こそ分かりにくいですが、ゲームとしてみるとNimKです。
この記事を読んで理解した方なら”やるだけ”ですね！(実際にはPOJ特有のアレや問題文がアレなのでやるだけではないかも)

明日は575検出のプロ、YazatenさんのICPC引退ポエム？です。

[追記]

組合せゲームの勉強に良さそうな本 (一般的なゲーム理論ではない方)

(A) 組合せゲーム理論入門
(B) 石取りゲームの数学
競技プログラミングから外れるものも多いので、一部分だけ読めばNim,grundy数のことがわかります。(ちゃんとインターネットに演習問題の答えもあって比較的やさしい)
ちゃんと読むと、Aでは AOJ-ICPC1000点問題が、Bでは Atcoder 1100点問題とかが解けるようになります(もちろん多少の前提知識があれば本を読まなくても考えると解けます(という人もいる))