Kazun の競プロ記録

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

AtCoder Beginner Contest 255 B問題 Light It Up

AtCoder ABC ABC255 B問題 200 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

N 人の人が座標平面上にいる. 特に, i 番目の人は座標 P_i=(X_i, Y_i) にいる.

また, A_1, A_2, \dots, A_K 番目の人計 K 人は同じ強さの明かりを持っている.

座標 (x,y) にいる人が強さ R の明かりを持っているとき, 中心 (x,y), 半径 R の円の内部 (境界含む) が照らされる.

以下の条件を満たすために必要な明かりの強さの最小値を求めよ.

  • 全ての人が少なくとも1個の明かりによって照らされている.

制約

  • 1 \leq K \leq N \leq 1000
  • 1 \leq A_1 \lt A_2 \lt \dots \lt A_K \leq N
  • |X_i|, |Y_i| \leq 10^5
  • i \neq j \Rightarrow P_i \neq P_j

解法

次の性質を使うことにする.

実数 x, a_1, \dots, a_n に対して, 以下が成り立つ.

  • x \geq a_i となる 1 以上 n 以下の整数 i が存在する \iff x \geq \min (a_1, \dots, a_n)
  • x \geq a_i が全ての 1 以上 n 以下の整数 i で成立する \iff x \geq \max (a_1, \dots, a_n)

2点 P,Q 間の距離を \operatorname{dist}(P,Q) と書くことにする. つまり, P=(x,y), Q=(x',y') としたとき,

\operatorname{dist}(P,Q)=\sqrt{(x-x')^2+(y-y')^2}

である.

このとき, 強さ が R のとき, 人 i が照らされるための必要十分条件は

1 \leq \exists j \leq K \quad {\rm s.t.} \quad \operatorname{dist}(P_i, P_{A_j}) \leq R

であるから, 上で述べた性質を利用して,

\displaystyle \min_{j=1,2, \dots, K} \operatorname{dist}(P_i, P_{A_j}) \leq R

である.

これが全ての人 i について成立しなければならないので,

\displaystyle 1 \leq \forall i \leq N; \quad \min_{j=1,2, \dots, K} \operatorname{dist}(P_i, P_{A_j}) \leq R

であり, 再び上で述べた性質を利用して,

\displaystyle \max_{i=1,2, \dots, N} \left(\min_{j=1,2, \dots, K} \operatorname{dist}(P_i, P_{A_j}) \right) \leq R

である.

以上から, \displaystyle \widetilde{R}:=\max_{i=1,2, \dots, N} \left(\min_{j=1,2, \dots, K} \operatorname{dist}(P_i, P_{A_j}) \right) としたとき, \widetilde{R} \leq R なる全ての実数 R において条件を満たすので, 求めるべき答えは \widetilde{R} である.

この \widetilde{R} を求めるために, 各 1 \leq i \leq N, 1 \leq j \leq K に対して, \operatorname{dist}(P_i, P_{A_j}) は O(1) で求められるので, \widetilde{R} を O(NK)=O(N^2) 時間で求められる.