AtCoder

ABC291 E問題(Find Permutation)を解く

AtCoder_ABC291_E

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

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

E問題 Find Permutation(Difficulty : 1069)

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

ABC291 D問題 Find Permutation

有向グラフの最長パスを求めることにより解くことができます。AtCoder Problems による Difficulty は 1069 でした。

解答案

以下は、公式解説の2つ目に挙げられているプログラムを参考にしています。

問題の入力例1の Xi から Yi への辺を持つグラフは以下の一本道になります。

2 → 3 → 1

この一本道の順序 Pi について、APi = i と定めた A が解答となります。入力例1の場合、A2 = 1、A3 = 2、A1 = 3 となり、Ai = (3, 1, 2) となります。これは、問題の状況をいくつか手書きしてみれば、理解できました。

一方、入力例2から、グラフが一本道にならない場合は、”No” になることが分かります。

一本道になる条件は、N頂点のグラフの一番長いパスが N – 1 になることと同値になります。これらを使って、問題を解いていきます。

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

上記の考察をプログラムとして表現しました。

普段は、グラフを vector<vector<int>> で表現していましたが、入力例3をみると、重複した辺があるため、vector<set<int>> で表現しました(5行目、28行目)。なお、その頂点が持つパスの長さの配列 path_legnth を、その頂点を調べ終えたかの判断に使っているため、辺が重複していてもプログラムは動作します。(vector<vector<int>> でも動作します。)

プログラムでは、頂点がもつパス長さを格納している配列 path_length から、数列を求めることができます。頂点のパス長さは、一本道にしたときの逆になっています。一番末尾は0になり、先頭は N – 1になるため、N から引けば、求める値となります。

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

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

#define N 200001
vector<set<int>> e(N);
vector<int> path_length(N, -1);

int dfs(int v)
{
	if (path_length[v] != -1) {
		return path_length[v];
	}
	path_length[v] = 0;
	for (auto next_v : e[v]) {
		path_length[v] = max(path_length[v], dfs(next_v) + 1);
	}

	return path_length[v];
}

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

	int max_path_length = 0;
	for (int i = 1; i <= n; ++i) {
		max_path_length = max(max_path_length, dfs(i));
	}

	if (max_path_length == n - 1) {
		cout << "Yes" << endl;
		for (int i = 1; i <= n; ++i) {
			cout << n - path_length[i] << " \n"[i == n];
		}
	} else {
		cout << "No" << endl;
	}

	return 0;
}

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

Python プログラム例(ABC291E)

Python 版は、C++ のプログラムをそのまま移植しました。再帰関数の呼び出し回数の上限を増やすために sys.setrecursionlimit を呼び出しています(5行目)。回数は余裕をみて設定しました。

"""AtCoder Beginner Contest 291 E"""
import sys

LIMIT = 10**6
sys.setrecursionlimit(LIMIT + 1)


def dfs(v):
    if path_length[v] != -1:
        return path_length[v]
    path_length[v] = 0
    for next_v in e[v]:
        path_length[v] = max(path_length[v], dfs(next_v) + 1)

    return path_length[v]


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

max_path_length = 0
for i in range(1, n + 1):
    max_path_length = max(max_path_length, dfs(i))

if max_path_length == n - 1:
    print("Yes")
    print_path = []
    for i in range(1, n + 1):
        print_path.append(n - path_length[i])
    print(*print_path)
else:
    print("No")

こちらも「AC」と判定されました。

最後に

有向グラフが1本道になることと、この問題で “Yes” になる条件と同値であることは、いくつか手書きでグラフを描いて気づきました。結果的には、時間切れとなりました。

コンテスト後、公式解説を参考にして理解することができました。

引き続き ABC に挑戦して、解説記事を書いていくつもりです。

COMMENT

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

CAPTCHA