Kazun の競プロ記録

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

AtCoder Beginner Contest 304 C問題 Subscribers

AtCoder ABC ABC304 C問題 300 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

座標平面上に $N$ 人の人がいる. 人 $i$ は座標 $(X_i, Y_i)$ にいる.

ウイルス V は感染した人から (Euclid) 距離で $D$ 以下にいる人全てに感染させる能力を持っている.

ある時, 人 $1$ がウイルス V に感染した. そして, 十分長い時間が経過した時, 各人はウイルス V に感染しているか?

制約

$1 \leq N \leq 2000$
$1 \leq D \leq 2000$
$-1000 \leq X_i, Y_i \leq 1000$
$i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)$

解法

実際に, 人 1 から距離が $D$ 以下の人に対して, ウイルス V を感染させていくシミュレーションを行えば良い. ただし, 一度感染したひとに関する調査はスキップしなければならない.

ちなみに, これはあるグラフ上の BFS となる, 実際, 次のような無向グラフ $G=(V,E)$ における頂点 $1$ が属する連結成分を調べていることと同等である.

$V:=\{1,2, \dots, N\}$
$E:=\{ij \mid (X_i-X_j)^2+(Y_i-Y_j)^2 \leq D^2 \}$

$G$ は $E$ の辺の構成について, 全ての組み合わせについて見る必要があるので, $O(N^2)$ 時間かかり, 最大で $\dfrac{N(N+1)}{2}$ 本となる.

よって, 計算量は BFS によって, $O(N^2)$ 時間となる.