ABC 354 E — Remove Pairs

考察

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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Remove Pairs の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: ゲーム状態の勝敗とGrundy数

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: game状態・Grundy DP

    補助タグ: 部分集合・bitmask状態DP

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: ゲーム状態の勝敗とGrundy数

    • 後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。

    先に読む単元:

    • 最小十分状態からDPを設計する — 初歩的な一次元DPを土台に、未来を決める情報だけを残す最小十分状態の設計原則を学ぶ。
    • 部分集合・bitmask状態DP — DPの最小十分状態で得た考え方と実装を再利用し、部分集合・bitmask状態DPの発動条件・正当化・境界を重複なく学ぶ。

    この解説で扱わないこと:

    • 有限DAGの得点差minimax、循環ゲームの距離評価、独立な数ゲームの加算。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題