典型タグ

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へ混同しない。

学習成果と学習単位

代表問題

この典型の考え方を具体的な問題で確かめるための入口です。

関連問題

この典型が主タグまたは補助タグとして付いている問題です。