AtCoder が提供しているABC（AtCoder Beginner Contest）304 のC問題をC++とPythonで解いてみました。ABC304は、2023年6月3日21:00に実施されました。
この回は、サーバ攻撃を受けてジャッジ遅れが大きく発生したため、unrated となりました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Virus（Difficulty : 366）
問題はリンク先をご覧ください。
グラフの問題として考えると、ある頂点と連結している頂点を求める問題に帰着します。AtCoder Problems による Difficulty は 366 でした。
解答案
人がいる場所をグラフの頂点と考えます。頂点間の距離が D 以下であれば、その頂点は隣接している（向きがない辺がある）とします。
人1がウィルスに感染すると、最終的に人1と連結している頂点はすべて感染します。連結していない頂点には感染しません。連結している頂点は、DFSでもBFSでも求めることができます。
C++ プログラム例（ABC304C）
問題文は人1からカウントしていますが、配列は0からカウントすることにします。以下の手順で処理をします。
- 頂点間の距離がD以下の場合、辺を設定する（30-33行目）。
- DFSを使って、頂点0と連結している頂点を求める（38行目と関数dfs）。
- 連結している頂点は “Yes” を、連結していない頂点は “No” を出力する（39-45行目）。
以下が、C＋＋プログラムとなります。プログラムは長く感じるかもしれませんが、多くのコードは、DFSを使ってグラフを取り扱う場合の定型コードです。
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
vector<bool> seen;
void dfs(int v)
{
seen[v] = true;
for (auto next_v : G[v]) {
if (!seen[next_v]) {
dfs(next_v);
}
}
}
int main()
{
int n, d;
cin >> n >> d;
vector<int> x(n), y(n);
for (int i = 0; i < n; ++i) {
cin >> x[i] >> y[i];
}
G.resize(n);
seen.assign(n, false);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if ((x[i] - x[j]) * (x[i] - x[j])
+ (y[i] - y[j]) * (y[i] - y[j]) <= d * d) {
G[i].push_back(j);
G[j].push_back(i);
}
}
}
dfs(0);
for (int i = 0; i < n; ++i) {
if (seen[i]) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC304C）
Python 版は、C++ のプログラムを移植しました。Pyhon3 (3.8.2) ではTLEとなりました。PyPy3 (7.3.0) では、AC 判定となります。
Python3 では、TLEとなったテストケースは一つだけですが、多くのテストケースで1秒以上の時間がかかっていました（制限は2秒）。一方、PyPy3 では、TLE になったテストケースが、224msec で処理できていました。処理時間はばらつきますが、この問題については、10分の1程度の時間で処理できています。
"""AtCoder Beginner Contest 304 E"""
import sys
LIMIT = 10**4
sys.setrecursionlimit(LIMIT + 1)
def dfs(v):
seen[v] = True
for next_v in G[v]:
if not seen[next_v]:
dfs(next_v)
n, d = map(int, input().split())
x = []
y = []
for i in range(n):
tx, ty = map(int, input().split())
x.append(tx)
y.append(ty)
G = [[] for i in range(n)]
seen = [False] * n
for i in range(n):
for j in range(i + 1, n):
if (x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2 <= d ** 2:
G[i].append(j)
G[j].append(i)
dfs(0)
for i in range(n):
print("Yes" if seen[i] else "No")Python は、C++ と比較すると、再帰関数の処理が遅い場合があるのかもしれません。わたしは、グラフの問題は、可能な限り DFS（再帰）を使って解いていました。Python では、BFS（キュー）を使って解く方がよいのかもしれません。
試しにBFSを使って解いてみました。deque を使いました。dfsの呼び出しをキューの処理に置き換えました（20-28行目）。
残念ながら Pyhon3 (3.8.2) ではTLEとなりました。PyPy3 (7.3.0) では、AC 判定となりました。実行時間を比較しましたが、DFS版とそれほどの差はありませんでした。
"""AtCoder Beginner Contest 304 E"""
from collections import deque
n, d = map(int, input().split())
x = []
y = []
for i in range(n):
tx, ty = map(int, input().split())
x.append(tx)
y.append(ty)
G = [[] for i in range(n)]
seen = [False] * n
for i in range(n):
for j in range(i + 1, n):
if (x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2 <= d ** 2:
G[i].append(j)
G[j].append(i)
que = deque()
que.append(0)
seen[0] = True
while que:
now = que.popleft()
for next_v in G[now]:
if not seen[next_v]:
que.append(next_v)
seen[next_v] = True
for i in range(n):
print("Yes" if seen[i] else "No")わたしは、それほど Python に習熟しているわけではありませんが、AtCoder の環境では PyPy3 を使う方が無難かもしれません。
最後に
この問題は、少し前ならグラフの応用と気が付かずに、いろいろ計算していたと思います（そして結果的に解けない）。解くことができたので、進歩しているかもしれません。
引き続き ABC の問題を紹介していきます。
