競技プログラミングの不偏ゲーム(Nim, grundy数にまつわる)問題集

はじめに

ゲーム問題へのアプローチについて

ゲームの末尾から考えるとルールや必勝法がわかりやすいです。
Sprague-Grundyの定理によってプレイヤーごとに打つ手が変化しないような”二人完全情報不偏ゲーム”はNimberによってニムに帰着できます。
ゲームをあらかじめ先手必勝か後手必勝かを考えることができます。→これを読みました。

組合せゲーム理論入門 ?勝利の方程式?

作者: M.H.Albert,R.J.Nowakowski,D.Wolfe,川辺治之
出版社/メーカー: 共立出版
発売日: 2011/09/21
メディア: 単行本
クリック: 5回
この商品を含むブログ (1件) を見る

僕はゲームについてよくわかっていないことが多かったのでこれで何とかなりました。章末問題の答えもWebにアップロードされているのでお金があれば買ってなければ図書館や友人から借りるといいと思います。ゲームの末尾の考え方や拡張が丁寧に書かれているのでとても良い本だと思います。(競プロの主体で読むならば直接関係のない難しいところは読みとばしてもよいと思います。)賢い方や日頃以下の問題を解いている方は読まなくても組合せゲーム理論の基礎的な概念を理解しているようなので必要ないと思います。

また不偏でないゲームについても終局面を考えれば大体の問題を解くことができます。これはDPか再帰で求めることができます(ゲームが終了することを示すことができればDAGであるので。)

以下に問題のリンクを張ります。これらは難易度順ではなく本を読んだ上で僕が解いた順です。適当な解説はgithubにあげてあるので見たい人はみつけてください。

1. C: 笑いをとれるかな？ - AtCoder Regular Contest 013 | AtCoder

2. codeforces 399 div2 E Game of Stones

3. codeforces 417 div2 E Sagheer and Apple Tree

4. Codeforces Round #432 (Div. 2, based on IndiaHacks Final Round 2017) E Arpa and a game with Mojtaba

5. ICPC Regionals 2010 Asia Jakarta Playing With Stones

6. SPOJ.com - Problem MMMGAME

7. SPOJ.com - Problem MATGAME

8. No.2 素因数ゲーム - yukicoder

9. No.102 トランプを奪え - yukicoder

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