game状態・Grundy DP
各状態の勝敗またはGrundy数を後続状態から求める。
この典型を扱う単元: ゲーム状態の勝敗とGrundy数
検索別名: Nim、combinatorial game DP、ゲームDP、組合せゲーム
未知問からこの典型を見つける手掛かり
- 扱う対象
- ゲーム
- 先手
- 後手
- 手番
- 石
- 使う手掛かり
- mex
- 勝ち
- 手を選
- 負け
- 保つ不変量
- grundy
- xor
- 後続状態
- 求めるもの
- grundy
- 勝てる
- 勝者
- 適用しない条件
- bottleneck path
- minimax path
分類・前提・学習成果
分類と直接の前提
概念上の親: DP状態と遷移
関連する典型
- 偶奇不変量によるゲーム戦略: 後続局面を再帰計算してmexや勝敗を求める方法と、合法手数・終端量の偶奇から局面探索なしに勝敗を決める方法を区別する。
- 有限局面DAGのminimax: impartial gameのGrundy数と、双方の目的が異なる局面のminimax値を同じゲームDPへ混同しない。
学習成果と学習単位
後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。
ゲーム状態の勝敗とGrundy数で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC354 E「Remove Pairs」 公式問題主題: ゲーム状態の勝敗とGrundy数 / 主タグ
- ABC380 F「Exchange Game」 公式問題主題: ゲーム状態の勝敗とGrundy数 / 主タグ
- ABC297 G「Constrained Nim 2」 公式問題主題: ゲーム状態の勝敗とGrundy数 / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC212 H「Nim Counting」 公式問題主題: 分離可能線形変換・Walsh–Hadamard変換 / 補助タグ
技能・出典
主タグ: 分離可能線形変換・Walsh–Hadamard変換 / 補助タグ: game状態・Grundy DP、法上の四則演算・高速累乗・逆元
- ABC255 G「Constrained Nim」 公式問題主題: ゲーム状態の勝敗とGrundy数 / 主タグ
- ABC265 Ex「No-capture Lance Game」 公式問題主題: NTT・FFTで畳み込みと相互相関を求める / 補助タグ
技能・出典
主タグ: 畳み込み・相互相関 / 補助タグ: 独立な数ゲームの和、game状態・Grundy DP、分離可能線形変換・Walsh–Hadamard変換
- ABC278 F「Shiritori」 公式問題主題: ゲーム状態の勝敗とGrundy数 / 主タグ
- ABC278 G「Generalized Subtraction Game」 公式問題主題: ゲーム状態の勝敗とGrundy数 / 主タグ
- ABC297 G「Constrained Nim 2」 公式問題主題: ゲーム状態の勝敗とGrundy数 / 主タグ
- ABC354 E「Remove Pairs」 公式問題主題: ゲーム状態の勝敗とGrundy数 / 主タグ
- ABC368 F「Dividing Game」 公式問題主題: ゲーム状態の勝敗とGrundy数 / 主タグ
- ABC380 F「Exchange Game」 公式問題主題: ゲーム状態の勝敗とGrundy数 / 主タグ
- ABC433 G「Substring Game」 公式問題主題: Suffix Automatonで部分文字列集合を表す / 補助タグ