二人零和有限確定完全情報ゲームで、かつ、グランディー数が関係しないものを解析する。今の所、過去問並べただけ。
後退解析
遷移が有向グラフ \(G\) で表されるゲームの勝敗は \(v \in V(G)\) について
- \(v\) が負けのとき、\(v\) に遷移可能な頂点 \(\delta^-(v)\) は勝ち
- \(v\) から遷移可能な頂点 \(\delta^+(v)\) が全て勝ちのとき、\(v\) は負け
である。ゲームの終了条件が決められている頂点から順に決定すればよい。勝敗の確定しなかった頂点は、勝敗の確定しなかった頂点に遷移するのが最適である。従って、永遠に勝敗が決まらない。将棋ではこのような状態を避けるため、同一局面が4回現れると引き分けとする、千日手が設定されている。
DAGの後退解析
DAGの場合、後退解析は簡略化できる。閉路が存在しないので、勝敗が決まらない頂点は存在しない。
- ゲームの終了状態に、勝敗を割り振る。
- 勝敗が未確定の頂点を、一時的に、負け状態と仮定する。
- トポロジカル順序の逆順に頂点 \(v\) を見る。
- \(v\) が勝ちなら何もしない。\(v\) が負けなら、\(v\) に遷移可能な頂点を勝ちにする。
トポロジカル順序が自明ならば、手で勝敗が簡単に書き下せる場合がある。
DAGの後退解析をすればよい。先手の敗北条件は \(N = 0 \pmod {K+1} \) である。
DAGの後退解析。
DAGの後退解析。「直前に相手が \(x\) 個取り除いてなければ」勝ちという条件を論理和で配るので、各頂点の状態は
- 直前に相手が何個取り除いていようが、負け
- 直前に相手が \(x\) 個取り除いていれば、負け
- 直前に相手が何個取り除いていようが、勝ち
のいずれか。1つ目の状態が最短でも K+1 個おきにしか起きないので、更新回数は全体で \(O(N)\) になる。
解答略
DAGの後退解析。問題2の類題。
- 駒を辺に沿って動かす。
- ゲームを終了する。
のどちらかを選ぶ。十分長いターンが経ってもまだゲームが終了していないときは、強制終了する。ゲームが終了したときに、駒が置いてある頂点の数字(スコア)を先手は最大化、後手は最小化したい。数字はいくつになるか。(ARC038D)
スコアについて二分探索すると後退解析になる。
いくつかの根付き木が与えられる。交互に次のいずれかの操作を繰り返す。
- 1ターン目ならば駒を好きな木の根に置く。
- 葉でなければ、駒を子に移動する
- 葉であれば、まだ選ばれていない木の根に駒を移動する
操作できなくなったほうが負け。どちらが勝つか。
(Kupc2019E)
木の根を選び、葉まで駒を動かしてから、次の根を選ぶのが先手後手のどちらになっているか考える。
- 先手の意思で、先手後手を入れ替えることができる
- 先手の意思で、先手後手をそのままにすることができる
(True, True) を選ぶと先手の勝ち。(False, False) を選ぶと後手の勝ち。従って (False, False) が選ばれるのは最後。(True, False) ならば先手後手は必ず入れ替わる。(False, True) ならば先手後手は必ずそのまま。従って、(False, True) は勝敗と無関係。
勝敗の単調性
あるパラメータ A が大きいほど先手が有利(或いは不利)ならば、
- \(f_1(S, a) :=\) 状態 S でパラメータ A = a のときの勝敗
を持つ dp から
- \(f_2(S) :=\) 状態 S のとき、先手が勝つための A の最小値
を持つ dp に変更でき、状態数が減らせる。
N 個の石が相異なる非負整数座標 \(x_1, x_2, \ldots, x_N\) (\(0 < x_1 \leq \cdots < x_N\)) に置かれている。交互に、最も大きい座標に置かれている石を、他の石と重ならないように、より小さい非負整数座標に置き換える。操作できなくなったほうが負け。どちらが勝つか。
(ARC137C)
単調性より、\(x_N\) が大きいほど先手が有利。戦略盗みにより、\(x_N-x_{N-1} \geq 2\) ならば先手の勝ち。さもなくば、\(x_N-x_{N-1} =1\) を保ちながら遷移するしかないので、最適手は \(O(N)\) でシミュレートできる。
- 先手は好きな頂点を1つ選び書き込まれた数字を零にする。
- 後手は子に駒を移動する。葉に移動した場合はゲーム終了。葉でもなくとも、後手の意思で終了にできる。
ゲーム終了時点で駒がある頂点に書き込まれた数字が得点になる。先手は得点を最小化、後手は得点を最大化したい。何点になるか。(ABC246G)
得点はX点以上か?について二分探索して、後退解析。取り除ける頂点が多いほど先手は有利なので、dp[v] := (頂点 v の部分木でゲームをしたとき得点を X 未満にするには、予め何個の頂点の得点を零にしておく必要があるか) について dp ができる。
\(a_1, a_2, \ldots, a_N\) 個の石からなる山が \(N\) 個ある。Aさんは右端の山から好きな個数の石を取ることができ、Bさんは左端の山から好きな個数の石を取ることができる。交互に操作を行う。操作できなくなったほうが負け。どちらが勝つか。
(AGC048D)
指せる手の単調性より
- \(a_1\) が大きいほど A さんが有利
- \(a_N\) が大きいほど B さんが有利
だから、操作は
- 山から石を一つだけ取る
- 山から石を全て取る
のどちらかであるとしても勝敗は変化しない。
- 残っている山が \(l, \ldots, r\) 番目で、\(l\) 番目の山以外は初期状態と石の個数が同じである。A さん先手で、A さんの勝ちとなる \(a_l\) の最小値 \(f(l, r)\)
- 残っている山が \(l, \ldots, r\) 番目で、\(r\) 番目の山以外は初期状態と石の個数が同じである。B さん先手で、B さんの勝ちとなる \(a_r\) の最小値 \(g(l, r)\)
\(f(l, r-1), g(l+1, r)\) から \(f(l, r), g(l, r)\) が \(O(1)\) で求まる。
不変量に着目する
二部グラフ
二部グラフ上のゲームの場合、各部集合が何らかの不変量と関連していることが多い。特に、グリッドグラフが頻出である。
H = 1 の場合を考える。N = 1 のときは先手必勝。N = 2 のときは、
- (x+y) mod 2 = 0 に置かれた駒の個数 A
- (x+y) mod 2 = 1 に置かれた駒の個数 B
について、\(A \neq B \Leftrightarrow \) 先手必勝。一般の N について、(A, B) は、駒を動かすたびに (-1, 1), (1, -1), (-1, 0), (0, -1) の何れかが足される。A-B には、-2, 2, -1, 1 が足される。従って、\(A – B \neq 0 \pmod 3 \Leftrightarrow \) 先手必勝 が予想される。実際に正しいことが証明できる。
- s, t の点連結度が1のとき先手の勝ち。
- s, t の点連結度が2のとき、点連結度を1にしたほうが負けなので、その直前では、2つの内素な s-t パスだけになる。二部グラフなので、このときの頂点数はそれまでの操作によらない。従って勝敗も O(1) で分かる。
偶奇
偶奇が不変量に関連していることがある。
- すべての要素を 1 減らす。全ての要素が正整数である場合のみこの操作ができる。
- 正整数を一つ選び、1 減らす。
操作ができなくなった方が負け。どちらが勝つか O(1) で求めよ。
(KUPC2020春E)
(最小値、総和)の偶奇の遷移は下図のようになる。\(N\) の偶奇によらず二部グラフになる。最小値 0 だと、全要素を 1 減らす遷移ができないが、可能な遷移は部分グラフであるので、なお二部グラフである。
gcd で割らなければ、\(\sum (A_i – 1)\) 回操作ができる。gcd は常に奇数なので、\(A_i, A_i/\mathrm{gcd}(A)\) の偶奇は同じ。従って、\(\sum (A_i – 1) = 1 \pmod 2 \Leftrightarrow\) 先手の勝ち。
- 山を2つに分割する。
- 各山から石を一つ取り除く。ただし、各山に2つ以上の石がなくてはならない。
操作できなくなったほうが負け。どちらが勝つか。(出典 : yukicoder1852)
(i) : \(\min(a)=1\) のとき、 \(S := \sum (a_i-1)=1 \Leftrightarrow \) 先手の勝ち。
(ii) : \(\min(a) > 1\) のとき、\(a_1\) を \(1, a_1-1\) に分割すると、(i) の \(S \leftarrow S-1\) の場合に帰着される。従って、\(S\) が奇数なら先手の勝ち。さもなくば、\(\forall i, a_i \leftarrow a_i-1\) の操作しか先手はできず、後手に \(S \leftarrow S-N\) の状態で渡される。\(N\) が奇数なら、先手の負け。\(N\) が偶数なら、\(\min(a)\) の偶奇で勝敗が決する。
グラフGが与えられる。交互に辺を追加する。連結になった方が負け。どちらが勝つか。
(AOJ2376)
連結になる直前の連結成分の大きさが k, n-k とすると、追加された辺の本数は n(n-1)/2-|E|-k(n-k) である。n が奇数ならば、連結成分は偶数と奇数の大きさが一つずつなので、 n(n-1)/2-|E| = 0 mod 2 ⇔ 先手勝利 である。
- 偶サイズの連結成分の個数
- 奇サイズの連結成分の個数
- 連結成分の個数を変えずに追加できる辺の個数の偶奇
偶と偶をマージ (-1, 0, 1)
偶と奇をマージ (-1, 0, 1)
奇と奇をマージ (1, -2, 0)
連結成分内で辺を追加 (0, 0, 1)
これより、(0, 0, 0) のほうが (1, 1, 0)より作りにくそうに見える。奇成分は常に偶数個あるから、実際、偶数が一つでもある状態で回ってこれば、偶数が2つ以上にして相手に渡せる。他のケースはこれを元に理詰め。
Comments