考察
最後の各試合で選手の勝数は0または1増える。現在の最多をWとすると優勝勝数はWまたはW+1で、W−2以下の選手は候補にならない。選手をH(W勝)、L(W−1勝)、O(それ以下)に分け、HH,HL,HO,LL,LO,OOの試合数をm_0,…,m_5とする。
優勝勝数をVに固定すると、各試合が「整合する確率pとそのときの確定候補人数k」を持つか、「確率1/2で候補一人、残り1/2でゼロ」を持つ。後者を可変試合と呼ぶ。次の表で全場合が定まる。
例えばV=WではHLはLが勝つ場合だけ整合し、二人ともW勝になる。HHが一試合でもあれば必ずW+1勝が生まれ、このcaseの確率は0。
確定試合のpの積をP、候補人数の和をK、可変試合数をxとする。V=W+1では(P,K,x)=(1,m_0,m_1+m_2)。V=Wではm_0=0のとき(2^{−(m_1+m_2)},2m_1+m_2+m_3,m_4)である。可変試合の候補人数は二項分布になる。
可変試合にいる候補可能選手の優勝確率への寄与は
A(P,K,x)=P 2^{−x} Σ_{t=0}^{x−1} C(x−1,t)/(K+1+t)。
本人が候補になる1/2と、残るx−1試合の候補数tをまとめた式である。確定試合にいる選手は、整合条件下で候補になる確率qを使い
q B(P,K,x)=q P 2^{−x} Σ_{t=0}^{x} C(x,t)/(K+t)
を加える。候補人数0の項は優勝者がいないcaseなので除き、この式を使う実在候補選手がいるときはK≥1である。可変選手はAを全員で共有し、確定選手もq=1または1/2だけ違う。二つのVについて表から各選手へ配り、足せばよい。
階乗・逆階乗、2冪と候補人数の逆元を2Nまで前計算すると、二つの和を各O(N)で計算して2N選手へO(N)で配れる。
典型の発動条件
結果classの対称圧縮
発動条件: 独立二択試合が多数あり、参加者の初期状態が少数classに限られるとき。
試合をclass数へまとめ、個別勝敗をbinomial分布で数える。
候補人数での期待値分解
発動条件: 同率首位から一様に優勝者が選ばれる確率を求めたいとき。
候補に含まれる確率を候補総数ごとに求めて1/wを掛ける。
問題固有の要素
指数個の勝敗列も、最終threshold周辺の状態classだけ残すと独立なtypeとbinomial成功数へ縮約できる。
別の問題へ持ち帰る視点: tie-break期待値は候補集合を列挙せず、特定選手を含む候補人数分布を数える。
正当性
各試合は独立で、表は勝者二通りの結果から優勝勝数Vへの整合と候補人数を直接数えている。確定試合全体の整合確率はP、そのときの候補人数はK。可変試合の候補数はx回の公平Bernoulliの和なので二項分布。本人が候補になる場合だけ、総候補人数の逆数を掛けると、最後の公平な優勝決定で本人が選ばれる確率となる。可変選手は本人の試合を分離したA、確定選手は条件付き候補率qを掛けたBで数える。V=W,W+1は排反で全結果を覆うので二caseの寄与和が答え。
実装上の注意
- OはW−2以下の分類名であり、実際の勝数0と混同しない。Wが小さい場合も元の勝数からH,L,Oを判定する。
- V=Wでm_0>0ならcase全体を飛ばす。分母の人数0を評価しない。
- 一選手ごとに二項和を計算せず、A,Bをcaseごとに一度計算して表のqだけ掛ける。
- 先に所属classを計算し、対戦入力の左右に戻して確率を出力する。
復習の核
- W-2以下を捨てられる理由を確認し、各六classが二つの最多勝caseで候補者を何人作るか表にしてから公式へ落とす。
計算量と制約
時間
O(N)、六試合classごとの確率を候補人数w=0..Nで一度ずつ集計して同classの全選手へ共有する。
空間
O(N)、階乗・逆元・2冪。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\le N\le2\times10 ^ 5; 0\le A _ i\lt2N\ (1\le i\le 2N); All input values are integers.
出典