問題
考察
まずは愚直にシミュレーションした場合の計算量を考える
まずは愚直にシミュレーションすると計算量がどうなるかを考えます。
$i<j$となる全ての$(i,j)$の組み合わせで以下の条件を両方満たすものを全探索します。両方満たしている場合は人$i$も人$j$も感染したといえます。
- 人$i$と人$j$の少なくとも一方が感染している。
- 人$i$と人$j$との距離が$D$以内である。
この全探索を1セットとします。Nセット繰り返せば十分に時間が経過したといえます。なぜなら十分に時間が経過していない間は新規の感染者が少なくとも1人出てるはずだからです。
ここまで書いておきながらなんですが、この通りに実装すると計算量が$O(N^3)$となります。$N≦2000$であることから実行時間制限に間に合いそうにないです。そこで他の方針を立てていきます。
人を頂点に見立てたグラフを考える
前置きが長くなりました。ここから計算量を落としていきます。そのために各人を頂点に見立てたグラフを考えてみます。感染経路になりえるのは距離が$D$以内の人同士です。そこで距離が$D$以内の頂点との間に辺を張ってみます。そうすると人$1$の頂点と連結した頂点の人は十分な時間が経過した頃には感染したといえるはずです。人$1$の頂点と連結しているかどうかは(深さ優先探索をする)、(幅優先探索をする)、(Union-Findを使用する)のいずれかをすれば小さい計算量で済みます。
ここまでを踏まえて以下の方針で実装を進めます。
- サイズ$N$のUnion-Findを用意する。
- 人$i$と人$j$の距離が$D$以内となる頂点同士を連結する。
- 各人に対して人$1$と連結しているかを調べる。
この実装で進めれば2の部分が計算量$O(N^2)$で、それ以外は計算量が小さいため実行時間制限に十分間に合いそうです。
1つ注意点として、距離が$D$以内かどうかを判定するとき、ユークリッド距離の式をそのまま当てはめようとすると誤差が出る可能性があり、下手するとWAもあり得ます。$D,X_i,Y_i$の制約もそこまで大きくないため、判定する式を2乗したもので判定しましょう。具体的には以下の式です。
$$(X_i - X_j)^2 + (Y_i - Y_j)^2≦D^2$$
提出コード(コンテスト後)
ご不明点などがあれば教えていただけると幸いです。