AtCoder

ABC304 C問題(Virus)を解く

AtCoder_ABC304_C

AtCoder が提供しているABC(AtCoder Beginner Contest)304 のC問題をC++とPythonで解いてみました。ABC304は、2023年6月3日21:00に実施されました。

この回は、サーバ攻撃を受けてジャッジ遅れが大きく発生したため、unrated となりました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 Virus(Difficulty : 366)

問題はリンク先をご覧ください。

ABC304 C問題 Virus

グラフの問題として考えると、ある頂点と連結している頂点を求める問題に帰着します。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 を使う方が無難かもしれません。

最後に

この問題は、少し前ならグラフの応用と気が付かずに、いろいろ計算していたと思います(そして結果的に解けない)。解くことができたので、進歩しているかもしれません。

ABC304 について、引き続き問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA