E - Colinear Editorial
by 
Yukkku
乱択を使わない解法
準備
以下が成り立ちます.
- 答えとなる直線は高々3つしか存在しない
証明
前提: 2つの異なる直線は点を高々1つしか共有しません.
\(N\)が偶数の場合
\(N = 2M\)とします. 答えとなる直線は点を\(M+1\)個以上含むので, 答えとなる直線が2つあった場合, そのどちらかに含まれる点の個数は\(2(M+1) - 1 = N+1\)個以上になります. これは\(N\)より大きいため矛盾し, 背理法により答えとなる直線は高々1つと示せました.
\(N=3\)の場合
\(3\)つの点から過半数(\(2\)つ)を選ぶ組合せが\(3\)通りであることから, 過半数の点を通る直線の個数は\(3\)個以下になります.
\(N\)が\(5\)以上の奇数の場合
\(N = 2M-1\)とします. 仮定から\(M\ge3\)です. 答えとなる直線は点を\(M\)個以上含むので, 答えとなる直線が3つあった場合, そのどれかに含まれる点の個数は\(3M - 3 = N+M-2 \ge N+1\)個以上になります. これは\(N\)より大きいため矛盾し, 背理法により答えとなる直線は高々2つと示せました.
方針
\(S\)を点の集合としたとき, \(f(S)\)を\(S\)のうち過半数の点を含む全ての直線の集合とします. 分割統治的に\(f(A)\)を求めます.
\(\left|S\right| \lt 6\) の場合
\(S\)に含まれる\(2\)つの点を選ぶ組合せを総当たりすることで\(f(S)\)が求められます.
\(\left|S\right| \ge 6\) の場合
\(N \coloneqq \left|S\right|\) とします.
\(X\sqcup Y = S\), \(\left|X\right|=\left\lfloor\frac N2\right\rfloor\), \(\left|Y\right|=\left\lceil\frac N2\right\rceil\)となるように2つの集合\(X\), \(Y\)をとれます (ここで, \(X\sqcup Y\)は非交和). このとき\(\left|X\right|,\left|Y\right|\ge3\)になります.
過半数の性質から, \(f(S) \subseteq f(X) \cup f(Y)\) になります. そのため,
- \(f(X)\), \(f(Y)\) を求める.
- \(f(X) \cup f(Y)\)に含まれる直線全てについて, \(S\)全体で過半数の点を含むか調べる
とすることで\(f(S)\)を求めることができます.
準備で示した命題から\(\left|f(X)\cup f(Y)\right|\le6\)と定数で抑えられるため, 2.の計算量は\(O(N)\)になり, 全体で計算量は\(O(N\log N)\)です.
実装例 (Rust, 109ms)
posted:
last update: