Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 225 E 問題フ

AtCoder ABC ABC225 E問題 500 pts

問題

提出解答

問題の概要

$O$ を原点とする座標平面上において, 2点 $p,q$ を結ぶ線分を $L(p,q)$ と書く.

$N$ 個の図形 $F_1, \dots, F_N$ が与えられる. 各 $F_i$ は以下の線分の和集合である.

$L((x_i,y_i), (x_i-1, y_1) )$
$L((x_i,y_i), (x_i+1, y_1) )$

ここで, 各 $i$ に対して,

$\displaystyle G_i:=\bigcup_{p \in F_i} L(O,p)$

とする.

このとき, $1 \leq i_1 \leq \dots \leq i_k \leq N$ で, 以下の条件を満たすとき, $k$ の最大値を求めよ.

$1 \leq j, j' \leq k, j \neq j'$ ならば, $G_{i_j}$ の内部と $G_{i_{j'}}$ の内部は共通部分を持たない.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq x_i, y_i \leq 10^9$
組 $(x_i, y_i)$ は全て異なる.

解法

$a,b \geq 0$ に対して,

$m(a,b)=\begin{cases} \infty & (a=0) \\ \frac{b}{a} & (a>0) \end{cases}$

とする.

このとき, $1 \leq i,j \leq N, i \neq j$ に対して, 各区間 $I$ を $I=(m(x_i, y_i -1), m(x_i -1, y_i) )$ とすると, 以下は同値である.

$G_i$ の内部と $G_j$ の内部は共通部分を持たない.
2つの開区間 $I_i, I_j$ は互いに素である.

なお, 証明は $p \in F_i$ における $L(O,p)$ の傾きを見れば良い.

このことから, 以下の問題に帰着される.

$N$ 個の開区間 $I_1, \dots, I_N$ が与えられる. ここから, どの2つの区間を選んでも互いに素になるような選び方のうち, 要素数の最大値を求めよ.

これは区間スケジューリング問題と呼ばれており, 以下の解き方で解くことができる.

$I_i=(L_i, R_i)$ としたとき, $I_1, \dots, I_N$ を $R_1 \leq \dots \leq R_N$ となるように並び替える.
とし, 以下をの順に行う.
- $r \leq L_i$ ならば, 開区間 $I_i$ を採用し, $r \gets R_i$ と更新する.
採用した開区間の数を出力する.

計算量はソート部分がボトルネックになり, $O(N \log N)$ である.

ただし, $m(x_i -1, y_i)$ の並び替えは実数で比較すると, 誤差によって間違える可能性があるので, 座標平面上の点とみて, 偏角ソートで行う.