ABC 448 G — Conquest

考察

各 BAN 後の勝率は有限零和 game の値であり、相手の二択混合確率 x を固定すると各自戦略は一次式になる。したがって game 値は直線群の上包絡線の [0,1] 最小値で表せる。

採用する候補: 各相手 BAN j について直線の上包絡線を構築し、一つの自戦略 i を除いた game 値 V_{i,j} を包絡線の基底となる高々定数本だけ再計算する。残る 3×N game は重複列を除き定数規模の凸最適化で解く。

包絡線の最小点を支える直線は高々二本で、それ以外を一本除いても値が変わらないため、V の異なる列型は定数個しか生じない。

棄却する候補: 全 BAN 組ごとに一般線形計画を独立に解き、最後の game も N 列のまま処理する。

同じ包絡線を N 回再構築して高次時間となり、問題固有の二列 game と定数 basis 性を利用できない。

二列零和 game では相手混合率 x に対する最良応答が max_k L_k(x) で、その最小値が minimax value になる。

全直線の包絡線の最小点を決める basis S は高々二本で、i∉S なら L_i を除いた値 V_i は共通の y_0 である。

j=1..3 ごとに残る二列から各行の直線を作り、傾き順の上包絡線と最小点・support setを求める。support 行だけ除外版を個別計算し V_{i,j} を埋める。各jの例外は高々2行なので、三成分vectorの異なる型は例外行高々6個と通常型1個、合計高々7個である。重複型を消して最後のBAN gameを解く。

高橋君がB_jをBANする確率をp_jとすると、青木君はΣ_j p_j V_{i,j}を最小にするA_iをBANする。よって求める値はmax_{p_j≥0,Σp_j=1} min_i Σ_j p_j V_{i,j}。p=(x,y,1−x−y)と置き、0≤x≤1、0≤y≤1−xの三角形上でF(x,y)=min_i(xV_{i,1}+yV_{i,2}+(1−x−y)V_{i,3})を最大化する。

Fは一次式の最小なので凹関数。固定xでyを最大化する内側三分探索を行い、その最大値を外側でxについて最大化する。内側最大値も凹である。二つの最適点を結ぶ点は三角形内にあり、Fの凹性で対応する値の線形補間以上を達成できるからである。各探索で端点も評価し、勝率を[0,1]へ正規化して例えば各100回探索する。残る幅は(2/3)^100<3×10^−18で、内側誤差も最終出力の許容誤差より十分小さくする。

典型の発動条件

零和 game の包絡線化

発動条件: 一方の純粋戦略が二つで混合率を一変数にできるとき。

最良応答を一次式の上包絡線として minimax 値を求める。

最適解 basis の除外 query

発動条件: 全要素集合の凸最適値から一要素除外値を全件求めたいとき。

最適点を支える定数個だけ再計算し、他は共通値とする。

問題固有の要素

game の混合戦略を直接列挙せず、低次元側の確率を座標にすると相手の最良応答が凸包・包絡線になる。

別の問題へ持ち帰る視点: 凸最適解を支える制約が少数なら、一要素除外で答えが変わり得る要素も少数に限られる。

正当性

相手二列混合xに対し各行利得は一次式で、最良応答はそのmax。min_x max行がminimax値。凸包絡線の最小は端点の一本か交点の二supportだけで証明でき、それら以外を除いても最小値は保たれる。support行だけ再計算すれば全BAN値を得る。同じ三成分値vectorを統合しても戦略集合の凸包は変わらないので、定数サイズの最終零和gameへ縮約できる。

実装上の注意

  • 交点・同傾き・区間端0/1での最小を誤差込みで頑健に比較する。support が退化する場合も高々二本の例外を漏らさない。

復習の核

  • 二列 game の payoff を x の一次式へ展開し、包絡線最小点を支えない行を除いても値が不変な図を描いて確認する。

計算量と制約

時間

O(N log N+I²)の固定三列構造。各列BANの上包絡線と高々二support除去、最終定数サイズgameをI回探索。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq T \leq 500; 3 \leq N \leq 5 \times 10^4; 0 \leq X_{i,j} \leq 10^6; The sum of N over all test cases is at most 5 \times 10^4.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: Convex Hull Trick・直線包絡

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

    主タグ: Convex Hull Trick・直線包絡

    補助タグ: 基準解による変更影響の局所化

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

    学習の位置

    体系上の位置: Convex Hull Trick・直線包絡

    • 一次関数候補の傾き・交点順を保ち、query点で包絡線上の最適な直線を選べる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題