AtCoder が提供しているABC（AtCoder Beginner Contest）317 のC問題をC++とPythonで解いてみました。ABC317は、2023年8月26日21:00に実施されました。
ABC316は欠番になりました。AtCoderからのお知らせはこちらです。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Remembering the Days（Difficulty : 604）
問題はリンク先をご覧ください。
ABC317 C問題 Remembering the Days
すべての順列を全探索して、最大値を求めました。AtCoder Problems による Difficulty は 604 でした。
解答案
順列の順番に並べた頂点を全探索します。計算量は、$O(N N!)$ となりますが、$2 \leqq N \leqq 10$ であるため間に合います。
実装上のポイントは、以下となります。
- 街の番号は、0 からカウントします。
- 道の長さを二次元配列 cost として格納しておきます。
- 0 から N-1 までの順列を生成して、以下を行います。
- 順列に従い、街を移動する。道路がなければ、そこでループを抜ける。
- 道路があれば、移動距離を増やす。
- この順列の移動距離を、いままでの最大値と比較して更新する。
C++ プログラム例（ABC317C）
0 から n-1 の値を配列 p に格納します（20－23行目）。p を next_permutation に与えて、生成された順列を使います（36行目）。その順列に従う移動距離を計算して、最大値を更新します（27ー35行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
int n, m;
cin >> n >> m;
vector<vector<ull>> cost(n, vector<ull>(n, 0));
for (int i = 0; i < m; ++i) {
int a, b, c;
cin >> a >> b >> c;
--a;
--b;
cost[a][b] = c;
cost[b][a] = c;
}
vector<int> p(n);
for (int i = 0; i < n; ++i) {
p[i] = i;
}
ull result = 0;
do {
ull this_result = 0;
for (int i = 0; i < n - 1; ++i) {
if (cost[p[i]][p[i + 1]] != 0) {
this_result += cost[p[i]][p[i + 1]];
} else {
break;
}
}
result = max(result, this_result);
} while (next_permutation(p.begin(), p.end()));
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC317C）
ABC302C問題でも、Python で順列を扱いました。同じように itertools モジュールを使います。
- itertools をインポートする（2行目）。
- すべての順列をリスト p_all に格納する（14行目）。
- p_all から順列 p を取り出して処理する（17行目）。処理はC++版と同じ。
以下のプログラムは、「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。
"""AtCoder Beginner Contest 317 C"""
import itertools
n, m = map(int, input().split())
cost = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
a, b, c = map(int, input().split())
a -= 1
b -= 1
cost[a][b] = c
cost[b][a] = c
num = list(range(n))
p_all = list(itertools.permutations(num))
result = 0
for p in p_all:
this_result = 0
for i in range(n - 1):
if cost[p[i]][p[i + 1]] != 0:
this_result += cost[p[i]][p[i + 1]]
else:
break
result = max(result, this_result)
print(result)最後に
公式解説では、DFSを使った全探索を行う方法を紹介していました。
再帰よりも、順列を使ったほうがすべての場合を探索していることが分かりやすいと感じました。このため、ブログではコンテストに提出した順列を使ったプログラムを紹介しました。
引き続き ABC の問題を紹介していきます。
