AtCoder

ABC270 C問題(Simple path)を解く

AtCoder が提供しているABC(AtCoder Beginner Contest)270 のC問題をC++で解いてみました。ABC270は、2022年9月24日21:00に実施されました。

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

C問題 Simple path(Difficulty : 625)

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

ABC270 C問題 Simple path

与えられたグラフから連結している頂点を探索する問題です。AtCoder Problems による Difficulty は、625 でした。ABC C問題としては、やや難しい難易度です。

解答案

問題を解く方針を書きだします。

  • 入力の読み込み(グラフの読み込み)
  • グラフの探索

グラフの表現は、隣接リスト表現と呼ばれる、頂点 u から隣接している集合 vector e[u] を定義する方法がよく使われます。N 個の頂点と N – 1 個の辺を持つグラフの入力をするコードは以下となります。なおこの問題では向きを持たないため、両方向の登録をしています(10行目と11行目)。

vector<int> e[N];

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

	return 0;
}

グラフの探索は、DFS(深さ優先探索:Depth-First-Search)を使う典型例となります。以下のコードでグラフの探索ができます。コードを読んで、動きを理解していただけたらと思います。

vector<int> e[N];
bool seen[N] = {false};

void dfs(int  v)
{
	seen[v] = true;
	for (auto next_v : e[v]) {
		if (!seen[next_v]) {
			dfs(next_v);
		}
	}
}

今回は、起点と終点が与えられて、その道筋を求めます。C問題としては難しいです。最終的なコードは以下となります。

C++ プログラム例(ABC270C)

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

#define N 200001

vector<int> e[N];
bool seen[N] = {false};

vector<int> path;
bool stop;

void dfs(int from, int to)
{
	if (!stop) {
		path.push_back(from);
	}
	if (from == to) {
		stop = true;
	}
	seen[from] = true;
	for (auto next_v : e[from]) {
		if (!seen[next_v]) {
			dfs(next_v, to);
		}
	}
	if (!stop) {
		path.pop_back();
	}
}

int main()
{
	int n, x, y;
	cin >> n >> x >> y;
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}

	stop = false;
	dfs(x, y);

	for (int i = 0; i < path.size(); ++i) {
		if (i != 0) {
			cout << " ";
		}
		cout << path[i];
	}
	cout << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

この C++ のプログラムを Python で書くのは、今のわたしでは難しいです。今回は、C++ のみの紹介とします。

最後に

グラフに慣れていない場合、C問題としては難しいと思います。

D問題は、貪欲法で最初解いて、それでは正解が出せない場合があることが分かりました。DP(動的計画法)を使う必要があり、Difficulty 1300 と判定されていました。解説をするには、自分の理解が足りていないため、今回は、C問題までの解説としました。

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

COMMENT

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

CAPTCHA