考察
過半数lineが存在するならrandomな異なる二点が両方そのline上にある確率は1/4より大きい。その二点が定めるlineを全点で検証すれば一試行O(N)である。
採用する候補: random pairを約100回sampleしてmajority lineを検証する
棄却する候補: 全点pairが定めるlineを調べる
O(N^3)検証、工夫してもpair O(N^2)がN=5×10^5に合わない。
異なるindex p,qをrandom sampleしa=y_p-y_q,b=x_q-x_p,c=x_p y_q-x_q y_pを作る。全点でax+by+c=0をcountし2count>NならYesと係数を出す。100回失敗ならNo。
典型の発動条件
Monte Carlo candidate sampling
発動条件: 解が多数要素に支持され、少数sampleで解を含む組を引ける。
二点sampleでcandidateを生成し、全入力によるdeterministic verificationを行う。
integer collinearity
発動条件: 座標line判定でfloating誤差を避けたい。
二点から整数係数を作りdeterminant式を64bitで評価する。
問題固有の要素
過半数lineが存在すれば、無作為な異なる二点がそのline上にある確率は1/4を超える。sampleで得たlineは全点を整数式で検証するため、過半数に達した候補だけをYesとし、候補の一意性を仮定しない。
別の問題へ持ち帰る視点: 多数派構造はrandom witness生成と厳密検証の組合せに向く。
正当性
line上点数m≥(N+1)/2ならpair hit確率m/N·(m-1)/(N-1)≥(N+1)/(4N)>1/4。hitしたcandidateはexact integer determinantで必ず認証でき、false positiveはない。 存在時の失敗確率を(3/4)^Tまで下げ、O(TN)で十分高速かつ高確率に正答する。
実装上の注意
- 二indexを必ず異ならせ、係数積は制約内64bitだが符号を含める。random seedの偏りを避ける。
復習の核
- 解あり/なしを小N全pair真値と比較し、100回失敗確率も評価する。
計算量と制約
時間
O(TN)、T=100、整数determinant検査。
空間
O(N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 3 \leq N \leq 5 \times 10^5; N is odd.; -10^8 \leq x_i \leq 10^8; -10^8 \leq y_i \leq 10^8; If i \neq j, then (x_i, y_i) \neq (x_j, y_j).; All input values are integers.
出典