AtCoder が提供しているABC（AtCoder Beginner Contest）337 のC問題をC++とPythonで解いてみました。ABC337は、2024年1月20日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Lining Up 2（Difficulty : 258）
問題はリンク先をご覧ください。
グラフの問題と考えて、DFS で経路を求めました。AtCoder Problems による Difficulty は 258 でした。
解答案
C++ プログラム例（ABC337C）
グラフの問題と考えて、DFS で経路を求めます。
- A[i] が -1 となる i は木の頂点となります。
- A[i] → i の頂点を設定します。
- 関数 dfs で経路を記録しながら探索します。グラフの形は、問題の設定から一本の形になります。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
vector<bool> seen;
vector<int> path;
void dfs(int v)
{
seen[v] = true;
path.push_back(v);
for (auto next_v : G[v]) {
if (!seen[next_v]) {
dfs(next_v);
}
}
}
int main()
{
int n;
cin >> n;
G.resize(n + 1);
seen.assign(n + 1, false);
int root = 0;
for (int i = 1; i <= n; ++i) {
int a;
cin >> a;
if (a == -1) {
root = i;
} else {
G[a].push_back(i);
}
}
dfs(root);
for (int i = 0; i < n; ++i) {
cout << path[i] << " \n"[i == n - 1];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC337C）
Python 版も基本的な考え方は同じです。再帰関数の呼出回数の上限を増やしました（2、4行目）。以下となります。
"""AtCoder Beginner Contest 337 C"""
import sys
sys.setrecursionlimit(10**6)
def dfs(v):
global G, seen, path
seen[v] = True
path.append(v)
for next_v in G[v]:
if not seen[next_v]:
dfs(next_v)
n = int(input())
G = [[] for _ in range(n + 1)]
seen = [False] * (n + 1)
path = []
a = list(map(int, input().split()))
for i in range(n):
if a[i] == -1:
root = i + 1
else:
G[a[i]].append(i + 1)
dfs(root)
print(*path)こちらも「AC」と判定されました。
最後に
グラフの問題に帰着して DFS で解いてみました。もっとプログラムを簡単にすることはできますが、手の内化した道具に使い慣れることを優先しました。
引き続き ABC の問題を紹介していきます。
