考察
N≤18 なので場に残るカード集合は2^N通り。手番以外の履歴は、現在どのカードが残っているかだけで次の合法手と勝敗が決まる。有限 impartial game では、現在から相手を負け状態へ送れる手が一つでもあれば勝ち、全て相手勝ちなら負けという後退解析が使える。mask から合法 pair i,j を消した next が losing なら、その手を選んで相手を負けにできるので mask は winning である。合法 pair がない空でない状態も、空集合と同じく手を打てず losing になるため、default false 初期化で扱える。
採用する候補: 残存集合 mask ごとに勝敗を持ち、取り除ける同属性 pair を全探索する bitmask DP を行う。
遷移先は必ず popcount が2小さい既計算状態で、O(2^N N²) が N=18 に収まる。
棄却する候補: ゲーム木を手順ごとに DFS し、同じ残存集合へ至る別順序も独立に探索する。
pair の削除順により同一状態が指数的に重複し、memoization なしでは状態数を大幅に超える。
win[0]=false とし、mask を popcount 昇順または数値昇順に走査する。mask 内の i<j で A_i=A_j または B_i=B_j なら next=mask xor(1<<i)xor(1<<j) を調べ、win[next]=false が一つでもあれば win[mask]=true。full mask で勝者を出す。
典型の発動条件
有限ゲームの winning/losing DP
発動条件: 各手で状態量が必ず減少し、完全情報・交互手番の normal play を解くとき。
相手の losing 状態へ移れるかを bool DP で判定する。
集合状態の bitmask
発動条件: 要素数が20以下で、操作が要素の削除として表せるとき。
残存要素を bit で持ち、pair removal を bit 演算で遷移する。
問題固有の要素
カードの並びや削除履歴は将来の合法手に影響せず、残存集合が game state の十分統計量である。
別の問題へ持ち帰る視点: ゲーム DP では、将来の手集合を完全に決める最小状態を探し、手数単調性で DAG 化する。
正当性
二枚除去で残り集合は必ず小さくなり、履歴や手番番号は合法手へ影響しない。手なしは負け。相手を負け集合へ送れる手があれば勝ち、なければどの手でも相手が勝つという帰納法が成立する。数値順でも bit を二つ消した mask は小さいため、依存先は計算済み。
実装上の注意
- 合法条件は A 一致または B 一致の OR。mask の数値昇順なら pair 削除後は必ず小さいことを確認し、同じカードを二度選ばない。
復習の核
- 「勝ち状態」を直接構成せず、相手を負けへ送れる一手の存在として書く。合法手なしの状態を初期条件として小さい mask から検算する。
計算量と制約
時間
N 枚。合法 pair の事前計算 O(N²)、全状態走査 O(N²2^N)。
空間
勝敗配列と合法 pair で O(2^N+N²)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 18; 1 \leq A_i, B_i \leq 10^9; All input values are integers.
出典