AtCoder が提供しているABC（AtCoder Beginner Contest）291 のE問題をC++とPythonで解いてみました。ABC291は、2023年2月26日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Find Permutation（Difficulty : 1069）
問題はリンク先をご覧ください。
有向グラフの最長パスを求めることにより解くことができます。AtCoder Problems による Difficulty は 1069 でした。
解答案
2024/5/2追記
解説の文が不正確になっていました。わたしの理解の範囲で正しい記述にしました。また、入次数が次々の0になる頂点を見つける別解も示しました。
以下は、公式解説の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;
}グラフのたどり方が一意になるとは、あるひとつの頂点だけ入次数が0になります。その頂点の辺を抜くと、次に別の一つの頂点だけの入次数が0になります。これを繰り返すことができれば、たどり方が一意になります。以下のプログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
set<pair<int, int>> xy;
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
xy.insert(make_pair(x, y));
}
vector<int> in(n + 1, 0);
vector<vector<int>> G(n + 1);
for (auto e : xy) {
G[e.first].push_back(e.second);
++in[e.second];
}
queue<int> que;
for (int i = 1; i <= n; ++i) {
if (in[i] == 0) {
que.push(i);
}
}
vector<int> result(n + 1, 0);
int index = 1;
while (!que.empty()) {
if (que.size() != 1) {
cout << "No" << endl;
return 0;
}
int now = que.front();
que.pop();
result[now] = index;
++index;
for (auto next_v : G[now]) {
--in[next_v];
if (in[next_v] == 0) {
que.push(next_v);
}
}
}
if (index > n) {
cout << "Yes" << endl;
for (int i = 1; i <= n; ++i) {
cout << result[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」と判定されました。
最後に
有向グラフのたどり方が一意になることと、この問題で “Yes” になる条件と同値であることは、いくつか手書きでグラフを描いて気づきました。結果的には、時間切れとなりました。
コンテスト後、公式解説を参考にして理解することができました。
引き続き ABC の問題を紹介していきます。
