ABC 313 F — Flip Machines

考察

X_j≠Y_j の機械を一度でもカード i に接続して選ぶと、最後に i に触る機械の二択対称性から、i の裏向き確率は過去によらず 1/2 になる。期待値はカードごとに独立に足せる。

確定反転 X=Y を有利な時だけ先に処理した後、機械で触ると得するカード Q と、|A−B|/2 だけ損するカード P に分かれる。N≤40 なので小さい側だけ指数探索できる。

採用する候補: |P| と |Q| の小さい側を選び、P の subset 全探索または Q-mask の bit DP を使い分ける meet-in-the-middle 型最適化を行う。

棄却する候補: M 台それぞれを使う/使わないで全 subset を探索する。

M は 10^5 で 2^M は不可能であり、同じ端点ペアの機械が期待値上同じ効果を持つことも無視している。

X=Y の機械による確定反転を有利なカードだけ適用し基準和を作る。D_i=|A_i−B_i|/2 と P,Q を定義し、Q-Q の隣接利益を確定する。|P|≤|Q| なら全 P subset に対し −ΣD_P+ΣD_{隣接Q} を評価し、逆なら Q-mask DP で各 P の選択とその隣接 mask の OR を遷移する。最大増分を基準へ足す。

典型の発動条件

最後の乱択による確率のリセット

発動条件: 独立な確率1/2の反転を同じ対象へ複数回適用するとき。

最後に対象へ触る試行で parity が一様になるため、回数でなく一度でも触るかだけを見る。

二分割の小さい側を指数化

発動条件: 要素が利得側と損失側へ分かれ、全体 N は40程度のとき。

min(|P|,|Q|) の側に応じて subset 列挙と mask DP を切り替える。

問題固有の要素

確率過程が最終的に weighted vertex coverage へ落ち、機械の順序・重複が消えることが最大の簡約である。

別の問題へ持ち帰る視点: 確率1/2の反転を見たら parity 分布が最終試行で一様化しないか調べ、選択問題へ分離する。

正当性

P-P 辺は損だけなので不要、Q-Q 辺は利益だけなので採用してよい。P-Q 辺では触る P 集合を固定すれば、その P に隣接する全 Q を触るのが最適になる。 P が小さければその subset を直接評価し、Q が小さければ P を順に採否して現在覆われた Q-mask を持つ DP にする。 機械選択は「触れた頂点集合」の重み付き被覆へ帰着し、P∪Q=N より min(|P|,|Q|)≤20 を必ず利用できる。

実装上の注意

  • 期待値の 1/2 は double で扱うか全値を2倍して最後に割る。X=Y の確定反転を確率1/2扱いせず、処理後の表裏を基準に P,Q を作る。

復習の核

  • まず固定した機械集合の期待値をカード単位で完全に解く。最適化へ進むのは、各カードが「未接触/一様」の二状態になることを証明してからにする。

計算量と制約

時間

O(N²2^min(P,Q))、P,Qは有利/不利カード集合の小さい側mask。

空間

O(N²+2^min(P,Q))。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N \leq 40; 1\leq M \leq 10^5; 1\leq A_i,B_i \leq 10^4; 1\leq X_j,Y_j \leq N; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Flip Machines の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 候補数を界して全列挙・有限case分解する

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

    主タグ: 有界全列挙・有限case分解

    補助タグ: 寄与の数え上げと順序交換 部分集合・bitmask状態DP

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

    学習の位置

    体系上の位置: 候補数を界して全列挙・有限case分解する

    • 制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。

    先に読む単元:

    • 局所寄与へ分解して集計順を交換する — 数える対象を一意に固定し、その対象を含む選択や組の個数へ集計順を交換する。要素・組・区間・値のどれを固定すると重複が消えるかを比較する。
    • 部分集合・bitmask状態DP — DPの最小十分状態で得た考え方と実装を再利用し、部分集合・bitmask状態DPの発動条件・正当化・境界を重複なく学ぶ。

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

    • 探索空間を二つへ分けて照合するmeet-in-the-middle、および再帰部分問題へ分ける分割統治。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題