読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるNim/Grundy数問題まとめ

競技プログラミング

Nim/Grundy

本質を理解して無くても使うだけなら大丈夫。
どちらが勝つかを判定するような問題で使える。
HackerRankのGame Theoryも練習としていい。
hamayanhamayan.hatenablog.jp

Nim

N個の石山があり、交互に山から石を任意個取っていく。
先に取れなくなったほうが負け。
各石山の個数をx[i]個とすると、勝敗は各山の個数を全てxorした値を見れば分かる。
全てxorして=0なら先手は負け、!=0なら勝ち。
これだけ。

Nim問題

yukicoder No.2 素因数ゲーム

http://yukicoder.me/problems/no/2

ARC 013 C. 笑いをとれるかな?

http://arc013.contest.atcoder.jp/tasks/arc013_3

Grundy

2人でやるようなゲームではGrundy数に帰着させることでNimの原理で解ける場合がある。
Grundy数を以下のように定める

  • 負け状態のGrundy数は0
  • ある状態のGrundy数はそこから遷移可能な状態のGrundy数の中で最小の非負整数

大体のGrundy数の問題はこれを愚直に求めることで解ける。
あと、grundy数とNimにおける石の数は同じ意味である。

Grundy数問題

yukicoder No.103 素因数ゲーム リターンズ

https://yukicoder.me/problems/no/103

yukicoder No.361 門松ゲーム2

http://yukicoder.me/problems/1016

yukicoder No.102 トランプを奪え

http://yukicoder.me/problems/no/102

yukicoder No.153 石の山

http://yukicoder.me/problems/no/153

Misere Nim

最後に石を取ると負けとしたNimのこと。よく分かる解説。
http://sigma425.hatenablog.com/entry/2014/12/07/132702
http://winjii.hatenablog.com/entry/2016/05/29/143653
簡単には、

  • 積まれている石の数が2以上のものがあれば普通のNim
  • 全部1の場合は山の偶奇によって勝敗が分かる

実装

int N; cin >> N;
int g = 0, ma = 0;
rep(j, 0, N) {
	int s; cin >> s;
	g ^= s;
	ma = max(ma, s);
}

if (ma == 1) {
	if (N % 2) printf("Second\n");
	else printf("First\n");
} else {
	if (g != 0) printf("First\n");
	else printf("Second\n");
}