\(f(i,j)\) を \((i,j)\) が BAN されたときの利得とします．まずはこれを求めます．

[1] BAN 後のゲームの解き方

高橋君は \(p_i(x_i,y_i)\) をたくさん持っている．青木君は \(x\) 座標，\(y\) 座標のどちらかを確率的に選ぶ．という状況です．

まず微小な \(\varepsilon\) によるタイブレイクによって，\(p_i\) は一般の位置関係（どの \(3\) 点も同一直線上にない）だと考えて考察すればよいです．ただし実装で \(\varepsilon\) を足すことは必要ありません．

最適解となる戦略対を固定したとき，高橋君の混合戦略では青木君の戦略に対する最適反応戦略でなければいけません．このことから，高橋君が正の確率で混合する戦略は，あるベクトルとの内積を最大化する点であることが分かります．

このことから，点群 \(p_i\) の凸包をとり，隣接する高々 \(2\) 点の混合戦略を試す．という方法で解を求められます．

これを踏まえて高橋君の max-min 戦略を考えます．高橋君が混合する \(2\) 種以下を固定すると，混合する確率を \(p,1-p\) として，ある上凸関数 \(g(p)\) の最大化という問題になります．\(g\) は \(2\) 個の \(1\) 次関数の \(\min\) なので上凸です．その \(\max\) の計算は直線の交点などを計算することで計算もできますし，三分探索などでもよいです．

[2] すべての \(f(i,j)\) を求める

\(j\) を固定して，すべての \(i\) に対する \(f(i,j)\) を求めましょう．

まず，「どの \(p_k\) も BAN しない場合」の最適解において混合する高々 \(2\) 種の \(p_i,p_j\) を求めます．このとき，BAN するもの \(p_k\) が \(i\neq k,j\neq k\) を満たすなら，そのまま \(p_i,p_j\) の混合戦略を採用できます．

• 「どの \(p_k\) も BAN しない場合」を解く（混合する\(p_i,p_j\) も求める）
• 「\(p_i\) を BAN する場合」を解く
• 「\(p_j\) を BAN する場合」を解く

とすればよいです．結果的に，\(f(-, j)\) は \(N-2\) 箇所で同じ値ということになります．問題の後半パートではこのことに注意した枝狩りも可能です（不要ですが）．

[3] ゲーム全体を解く

ナッシュ均衡において高橋君は max-min 戦略なので，高橋君が混合する確率 \((p,q,1-p-q)\) について，\(g(p,q)\) を最大化する問題として定式化できます．\(g\) は \(p,q\) に関する \(1\) 次関数の min となるので上凸で，\(2\) 変数関数を凸最適化すればよいです．やはり三分探索などで簡潔に実装できます．

[4] 実装例

• https://atcoder.jp/contests/abc448/submissions/73938789