AtCoder

ABC299 E問題（Nearest Black Vertex）を解く

 
AtCoder_ABC299_E

AtCoder が提供しているABC（AtCoder Beginner Contest）299 のE問題をC++とPythonで解いてみました。ABC299は、2023年4月22日21:00に実施されました。

この回は、外部からDDoS攻撃を受けてサーバが不安定になり unrated となりました。

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

目次
  1. E問題 Nearest Black Vertex（Difficulty : 1262）
  2. 解答案
  3. 最後に

E問題 Nearest Black Vertex（Difficulty : 1262）

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

ABC299 E問題 Nearest Black Vertex

グラフの頂点間の最短距離を求めて、距離により色を塗り分けて問題を解きます。AtCoder Problems による Difficulty は 1262 でした。

解答案

N 個の頂点と M 本の辺から成る無向グラフに対して、K 個の頂点 pi と距離 di が与えられたときに、以下の頂点の塗分けができるか判定する問題です。

  • 頂点 pi から距離 di 未満の頂点はすべて白に塗る。
  • 頂点 pi から距離 di の頂点の少なくともひとつは黒に塗る。
  • 頂点の少なくともひとつは黒に塗る。

C++ プログラム例（ABC299E）

プログラムは以下の流れとなります。

  • BFS（幅優先探索：Breadth-First search）で頂点 pi からすべての頂点への距離を求めます（41-53行目）。
  • 先に頂点 pi から距離 di 未満の頂点はすべて白に塗ります（55-58行目）。
  • 頂点 pi から距離 di の頂点の少なくともひとつは黒に塗ることができるか確認します（62-70行目）。※先に白に塗ってある頂点は黒に塗ることができません。
  • 黒に塗ることができなければ、”No” を出力して終了します（71-74行目）。

この問題は、制約から K が 0 の場合があります。K が 0 の場合は、すべての頂点を黒にして、”Yes” を出力して終了します（28-35行目）。

以下が、C＋＋プログラムとなります。

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> G;
vector<vector<int>> dist;

int main()
{
	int n, m;
	cin >> n >> m;
	G.resize(n + 1);
	dist.resize(n + 1);
	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}

	int k;
	cin >> k;
	vector<int> p(k);
	vector<int> d(k);
	for (int i = 0; i < k; ++i) {
		cin >> p[i] >> d[i];
	}

	if (k == 0) {
		cout << "Yes" << endl;
		for (int i = 1; i <= n; ++i) {
			cout << 1;
		}
		cout << endl;
		return 0;
	}

	vector<int> color(n + 1, 0); //0:undefined -1:White 1:Black
	for (int i = 0; i < k; ++i) {
		dist[p[i]].assign(n + 1, -1);

		queue<int> que;
		que.push(p[i]);
		dist[p[i]][p[i]] = 0;
		while (!que.empty()) {
			int now = que.front();
			que.pop();
			for (auto next_v : G[now]) {
				if (dist[p[i]][next_v] == -1) {
					que.push(next_v);
					dist[p[i]][next_v] = dist[p[i]][now] + 1;
				}
			}
		}

		for (int j = 1; j <= n; ++j) {
			if (dist[p[i]][j] < d[i]) {
				color[j] = -1;
			}
		}
	}
	for (int i = 0; i < k; ++i) {
		bool found = false;
		for (int j = 1; j <= n; ++j) {
			if (dist[p[i]][j] == d[i]) {
				if (color[j] != -1) {
					found = true;
					color[j] = 1;
				}
			}
		}
		if (!found) {
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;
	for (int i = 1; i <= n; ++i) {
		if (color[i] == 1) {
			cout << 1;
		} else {
			cout << 0;
		}
	}
	cout << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

【参考】Warshell Floyd 法を使う場合

上記の例では、頂点 pi からすべての頂点の最短距離を BFS で求めました。

すべての頂点間の距離を求める Warshell Floyd 法も試しました。Warshell Floyd 法は、簡単なロジックですべての頂点間の最小距離を求めることができます（8-19行目）。アルゴリズムの詳細は紹介しませんが、プログラムは以下となります。

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

#define INF (1LL << 60)

void Warshell_Floyd(int n, vector<vector<ll>>& dist)
{
	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if ((dist[i][k] < INF)&&(dist[k][j] < INF)) {
					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}
	}
}

int main()
{
	int n, m;
	cin >> n >> m;

	vector<vector<ll>> dist(n, vector<ll>(n, INF));
	for (int i = 0; i < n; ++i) {
		dist[i][i] = 0;
	}
	for (int i = 0; i < m; ++i) {
		int s, t;
		cin >> s >> t;
		--s;
		--t;
		dist[s][t] = 1;
		dist[t][s] = 1;
	}

	int k;
	cin >> k;
	vector<int> color(n, 0); //0:undefined -1:White 1:Black
	vector<int> p(k);
	vector<int> d(k);
	for (int i = 0; i < k; ++i) {
		cin >> p[i] >> d[i];
		--p[i];
	}

	if (k == 0) {
		cout << "Yes" << endl;
		for (int i = 0; i < n; ++i) {
			cout << 1;
		}
		cout << endl;
		return 0;
	}

	Warshell_Floyd(n, dist);

	for (int i = 0; i < k; ++i) {
		for (int j = 0; j < n; ++j) {
			if (dist[p[i]][j] < d[i]) {
				color[j] = -1;
			}
		}
	}
	for (int i = 0; i < k; ++i) {
		bool found = false;
		for (int j = 0; j < n; ++j) {
			if (dist[p[i]][j] == d[i]) {
				if (color[j] != -1) {
					found = true;
					color[j] = 1;
				}
			}
		}
		if (!found) {
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;
	for (int i = 0; i < n; ++i) {
		if (color[i] == 1) {
			cout << 1;
		} else {
			cout << 0;
		}
	}
	cout << endl;

	return 0;
}

このプログラムは、いくつかのテストケースでTLE（Time Limit Exceeded）判定となりました。

Warshell Floyd 法はグラフの頂点数 $N$ に対して、$O(N^3)$ の計算量が必要となります。制約から $N \leqq 2000$ となっています。$N = 2000$ の場合、$N^3 = 8 \times 10^9$ となり時間的にはぎりぎりとなります。

Python プログラム例（ABC299E）

C++のロジックをそのまま Python に書き直しました。

残念ながら、Python (3.8.2) では、TLEとなります。PyPy3 (7.3.0) で AC 判定となります。

"""AtCoder Beginner Contest 299 E"""
import sys
from collections import deque

n, m = map(int, input().split())
G = [[] for i in range(n + 1)]
dist = [[-1 for j in range(n + 1)] for i in range(n + 1)]
for i in range(m):
    u, v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)

k = int(input())
p = [0] * (n + 1)
d = [0] * (n + 1)
for i in range(k):
    p[i], d[i] = map(int, input().split())

if k == 0:
    print("Yes")
    temp = [1] * n
    print(*temp, sep='')
    sys.exit()

color = [0] * (n + 1) #0:undefined -1:White 1:Black
for i in range(k):
    que = deque()
    que.append(p[i])
    dist[p[i]][p[i]] = 0
    while len(que) > 0:
        now = que.popleft()
        for next_v in G[now]:
            if dist[p[i]][next_v] == -1:
                que.append(next_v)
                dist[p[i]][next_v] = dist[p[i]][now] + 1

    for j in range(1, n + 1):
        if dist[p[i]][j] < d[i]:
            color[j] = -1

for i in range(k):
    found = False
    for j in range(1, n + 1):
        if dist[p[i]][j] == d[i]:
            if color[j] != -1:
                found = True
                color[j] = 1
    if not found:
        print("No")
        sys.exit()

print("Yes")
for i in range(1, n + 1):
    if color[i] == 1:
        print("1", end="")
    else:
        print("0", end="")
print("")

最後に

この問題は、コンテスト中に解くことができませんでした。色を塗るループを1回で処理しようとして、WAを取ることができませんでした。後で、すべての頂点に対して、白に塗れる頂点は先に塗ることに気づきました。

コンテストで解くことはできませんでしたが、学べました。

引き続き ABC の問題を紹介していきます。

ABC E問題 BFS C++ Python Warshell Floyd 法 グラフ プログラミング 最短経路を求める 難易度:水
関連記事はこちら

COMMENT

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

CAPTCHA