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

hamayanhamayan's blog

競技プログラミングにおけるゲーム問題まとめ [Nim,Grundy数,後退解析]

ゲーム問題を解決する手段

  • Nim
    • 「N個の石山があり、交互に山から石を任意個取っていく。先に取れなくなったほうが負け。」
    • 各石山の個数をx[i]個とすると、勝敗は各山の個数を全てxorした値を見れば分かる。全てxorして=0なら先手は負け、!=0なら勝ち
    • Nimの派生
  • Grundy
    • 2人でやるようなゲームではGrundy数に帰着させることでNimの原理で解ける場合がある
    • Grundy数を以下のように定める
      • 負け状態のGrundy数は0
      • ある状態のGrundy数はそこから遷移可能な状態のGrundy数の中で最小の非負整数
    • grundy数とNimにおける石の数は同じ意味
    • 高さLの完全二分木のgrundy数はL&-L
    • 規則性
      • ある周期になっている
  • 後退解析、バックトラック 参考
    • 状態の遷移先に負け状態が1つでもあれば、相手を負けにできるので勝ち状態
    • 逆に遷移先が全て勝ち状態ならば、自分は負けるしか無い
  • 特殊な勝ち負け
    • 偶奇を使う
    • 相手の行動を真似ると負けない

【発展的話題】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");
}