AtCoder が提供しているABC（AtCoder Beginner Contest）305 のF問題をC++とPythonで解いてみました。ABC305は、2023年6月10日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 Dungeon Explore（Difficulty : 1420）
問題はリンク先をご覧ください。
インタラクティブな問題ですが、DFSで頂点を探索することにより解けます。AtCoder Problems による Difficulty は 1420 でした。
解答案
インタラクティブな問題です。
まず、頂点の数 N と辺の数 M が与えられます。次に頂点1に隣接する頂点が与えられます。その隣接する頂点からひとつ選んで移動します。次の頂点を出力すると、その頂点に隣接する頂点が与えられます。
一度訪れた頂点を候補から外して移動すると、結果的にこのグラフは木になります。この場合、辺の数は N ー 1 となります。結果的に、移動の最大回数は 2 ×（N ー 1）回となります。
C++ プログラム例（ABC305F）
関数 dfs は、対象となる頂点 v とその親の頂点 r を引数に持ちます。
- 頂点 v を訪問済にする（9行目）。
- もし v と n が等しければ文字列を読み込み終了する（11－15行目）。
- v と隣接している頂点を読み込む（17－24行目）。
- 各頂点に対して次の処理を行う（26－31行目）。
- その頂点が訪問済でない場合、その頂点を出力して探索する（28、29行目）。
- 親の頂点を出力する。隣接する頂点は読み捨てる（33－39行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<bool> seen;
void dfs(int v, int r)
{
seen[v] = true;
if (v == n) {
string s;
cin >> s;
exit(0);
}
int k;
cin >> k;
vector<int> G;
for (int i = 0; i < k; ++i) {
int next_v;
cin >> next_v;
G.push_back(next_v);
}
for (auto next_v : G) {
if (!seen[next_v]) {
cout << next_v << endl;
dfs(next_v, v);
}
}
cout << r << endl;
int temp_k;
cin >> temp_k;
for (int i = 0; i < temp_k; ++i) {
int temp_v;
cin >> temp_v;
}
}
int main()
{
cin >> n >> m;
seen.assign(n + 1, false);
dfs(1, 1);
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC305F）
C++ 版を移植しました。Python は、再帰回数の呼び出し回数の上限が1000回ですが、N が100以下なので、この回数を増やす必要はありません。
プログラムを抜けるため、sys.exit() 関数を使っています（2、10行目）。
"""AtCoder Beginner Contest 305 F"""
import sys
def dfs(v, r):
seen[v] = True
if v == n:
input()
sys.exit(0)
k = list(map(int, input().split()))
for i in range(1, len(k)):
if not seen[k[i]]:
print(k[i])
dfs(k[i], v)
print(r)
input()
n, m = map(int, input().split())
seen = [False] * (n + 1)
dfs(1, 1)こちらも「AC」と判定されました。
最後に
F問題を紹介するのは初めてです。
この問題は、インタラクティブな受け答えをする必要がありますが、一度訪問した頂点を訪問しないという工夫をするだけで解くことができました。ただし、インタラクティブな問題は、正しく実装できているかを確かめることが普通の問題よりも難しいと考えています。
引き続き ABC の問題を紹介していきます。
