Kazun の競プロ記録

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

AtCoder Beginner Contest 243 C問題 Collision 2

AtCoder ABC ABC243 C問題 300 pts

問題

提出解答

問題の概要

$N$ 人の人が座標平面上の異なる地点におり, $i$ 番目の人は $(X_i, Y_i)$ にいる. また, それぞれの人は右か左を向いており,

$S[i]={\tt R}$ ならば右を向いている
$S[i]={\tt L}$ ならば左を向いている

確認が同じ速さで等速直線移動しはじめたとき, 衝突は発生するか?

制約

$2 \leq N \leq 2 \times 10^5$
$0 \leq X_i, Y_i \leq 10^9$
$i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)$
$S$ は ${\tt L}, {\tt R}$ からなる長さ $N$ の文字列

解法

衝突が発生することの必要十分条件は以下である.

次を満たすような2つの整数 $i,j$ が存在する.

$1 \leq i \lt j \leq N$
$Y_i=Y_j$
$X_i \gt X_j$
$S[i]={\tt L}, S[j]={\tt R}$

実はこれらは以下とも同値である.

次を満たすような整数 $y$ が存在する.

$\displaystyle \max_{\substack{1 \leq i \leq N \\ Y_i=y \\ S[i]={\tt L}}} X_i \gt \min_{\substack{1 \leq j \leq N \\ Y_j=y \\ S[j]={\tt R}}} X_j$

ただし, $\displaystyle \max \emptyset=-\infty, \min \emptyset=+\infty$ とする.

上の条件を満たすような $y$ の候補は $Y_1, \dots, Y_N$ に限られるため, 各 $y$ 座標と向きごとに $x$ 座標の最大値や最小値を記録することにより判定できる.

辞書を用いて最大値や最小値を保存することにより, 時間計算量 $O(N)$ で判定できた.