AIで解説 AtCoder攻略　ゲーム理論

ゲーム理論ページの位置づけ

項目	内容
必修度	発展
学習目安	標準〜発展
前提	DP・再帰
対象問題	10問（推定値あり10問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	0
標準	0〜799	0
標準〜発展	800〜1199	2
発展	1200以上	8
未算出	—	0

手番ごとの勝敗を、勝ち状態・負け状態の遷移やGrundy数へ落とし込みます。確率DPや通常の最短路とは、状態の意味と遷移方向が異なります。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

ゲーム理論の見分け方

二人が交互に操作し、最終的な勝敗を問う
相手に負け状態を渡す選択がある
同じ状態の勝敗を何度も計算する

ゲーム理論の実装前チェック

先手・後手と終端状態を定義する
勝ち状態から遷移できる負け状態を探す
操作回数と状態数の上限を見積もる

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC270 D G. Stones（公式解説）を解きます。残り石の数ごとに、先手が取れる石を全て試します。相手に残る石の最大得点を引けば、その手を選んだときの自分の得点が分かります。

N, K = map(int, input().split())
moves = list(map(int, input().split()))

dp = [0] * (N + 1)
for stones in range(1, N + 1):
    for move in moves:
        if move <= stones:
            dp[stones] = max(dp[stones], stones - dp[stones - move])

print(dp[N])

状態N個と手K個を調べるのでO(NK)時間、メモリO(N)です。手順を直接列挙するより、同じ残り石数を再利用できます。

ゲーム理論の学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC427 D G. The Simple Game	公式解説	公式Editorialの方針を simple game minimax として整理する。	981
ABC368 F I. Dividing Game	公式解説	Official editorial intent is classified as impartial game sg.	1180
ABC398 E H. Tree Game	公式解説	Color the tree bipartitely and use the parity of legal same-color edge additions to select the winning first/second strategy.	1238
ABC270 D G. Stones	公式解説	残り石数ごとの先手最大取得数を勝ち負けの漸化式で計算する。	1300

次に解く

問題	公式解説	出題意図	difficulty
ABC349 E H. Weighted Tic-Tac-Toe	公式解説	Official editorial intent is classified as weighted tictactoe minimax.	1464
ABC390 D G. Stone XOR	公式解説	石の値のXOR不変量を利用し、勝敗を直接判定する。	1607
ABC380 F I. Exchange Game	公式解説	カードの手札・場の集合をビットマスク状態にし、手の有無を再帰メモ化で判定する。	1769

挑戦問題

問題	公式解説	出題意図	difficulty
ABC209 E Shiritori	公式解説	Build a graph on three-letter suffix/prefix states and propagate winning and losing states backward from terminal words.	2153
ABC206 F Interval Game 2	公式解説	For every interval [l,r), XOR the Grundy values of the two parts after selecting an allowed subinterval, then take mex.	2221
ABC418 F I. We’re teapots	公式解説	公式Editorialの方針を teapot game dp として整理する。	2496