AtCoder が提供しているABC（AtCoder Beginner Contest）318 のD問題をC++とPythonで解いてみました。ABC318は、2023年9月2日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 General Weighted Max Matching（Difficulty : 1017）
問題はリンク先をご覧ください。
ABC318 D問題 General Weighted Max Matching
DFSで全探索することで解くことができます。AtCoder Problems による Difficulty は 1017 でした。
解答案
頂点の数 $N$ には、$2 \leqq N \leqq 16$ という制約があります。
頂点が最大の16個ある場合を考えます。最初に選ぶ頂点を仮に1とします。 残りの頂点は15個あり、そこから一つの頂点を選ぶことによって辺を選ぶことになります。残りの頂点は14個あり、そこからもう一つの頂点を選ぶことによって、もう一つ辺を選びます。結果的に16個ある頂点から、8個の辺を選びます。この選び方は、
$$15 \times 13 \times 11 \times 9 \times 7 \times 5 \times 3 \times 1 = 2027025 $$
通りとなります。計算量的には間に合います。この8重ループは、バックトラックと呼ばれる再帰関数を使う手法で実現します。ABC310D（解説記事）でも使いました。
C++ プログラム例（ABC318D）
プログラムの解説です。
- 再帰関数 dfs の引数は、それまでの辺の重みの総和です。
- 頂点が使われているか配列 used で管理します。その配列を用いて、番号が一番小さい未使用の頂点 i を選びます（16ー20行目）。未使用の頂点が無くなれば戻ります。
- 残りの未使用の頂点 j を選び、次の辺を選ぶために再帰関数 dfs を呼びます（26ー32行目）。
- 未使用の頂点を「使用」にしてdfsを呼び出し、戻ってきたら「未使用」に戻します（バックトラック）。
- 頂点が奇数の場合は、すべて使い切るように頂点数を増やして偶数にします（46、47行目）。これは辺の重みがすべて0の頂点を加えることになるため総和に影響を与えません。
以下が、C＋＋プログラムとなります。キーとなる行の背景行を変更しました。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int n;
ull result = 0;
vector<vector<ull>> d(16 + 1, vector<ull>(16 + 1, 0));
vector<bool> used(16 + 1, false);
void dfs(ull w)
{
result = max(result, w);
int i, j;
for (i = 1; i <= n; ++i) {
if (!used[i]) {
break;
}
}
if (i > n) {
return;
}
used[i] = true;
for (j = i + 1; j <= n; ++j) {
if (!used[j]) {
used[j] = true;
dfs(w + d[i][j]);
used[j] = false;
}
}
used[i] = false;
return;
}
int main()
{
cin >> n;
for (int i = 1; i <= n - 1; ++i) {
for (int j = i + 1; j <= n; ++j) {
cin >> d[i][j];
}
}
if (n % 2 == 1) {
++n;
}
dfs(0);
cout << result << endl;
return 0;
}2024/5/2追記
別解として、bitDPに近い方法で解いてみました。bitDPの定番コードと異なり頂点 $j$ も $k$ も含まれていない場合に値を更新します（20ー33行目）。計算量は、こちらの方が速かったです。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
int n;
cin >> n;
vector<vector<ull>> d(n + 1, vector<ull>(n + 1, 0));
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
cin >> d[i][j];
}
}
if (n % 2 == 1) {
++n;
}
vector<ull> dp(1 << n, 0LL);
for (int i = 0; i < (1 << n); ++i) {
for (int j = 0; j < n; ++j) {
if (((i & (1 << j)) != 0)) {
continue;
}
for (int k = 0; k < n; ++k) {
if ((i & (1 << k)) == 0) {
int v = (i | (1 << j) | (1 << k));
dp[v]= max(dp[v], dp[i] + d[j][k]);
}
}
}
}
cout << dp[(1 << n) - 1] << endl;
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC318D）
C++のプログラムを移植しました。Python は再帰関数の呼出回数に1000回という制限がありますが、この問題ではその制限を拡張する必要はありませんでした。
以下のプログラムは、「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。
"""AtCoder Beginner Contest 318 D"""
def dfs(w):
global n
global result
global d
global used
result = max(result, w)
for i in range(1, n + 1):
if not used[i]:
break
else:
return
used[i] = True
for j in range(i + 1, n + 1):
if not used[j]:
used[j] = True
dfs(w + d[i][j])
used[j] = False
used[i] = False
return
n = int(input())
result = 0
d = [[0 for j in range(16 + 1)] for i in range(16 + 1)]
used = [False] * (16 + 1)
for i in range(1, n):
a = list(map(int, input().split()))
for j in range(i + 1, n + 1):
d[i][j] = a[j - (i + 1)]
if n % 2 == 1:
n += 1
dfs(0)
print(result)こちらも「AC」と判定されました。
最後に
公式解説は、bitDP で解く方法を紹介していました。今の私では、bitDPの解説が腹落ちせず、解説放送で紹介されている方法を紹介しました。バックトラックのよい復習になりました。2024/5/2追記 bitDP で解く方法も紹介できました。
引き続き ABC の問題を紹介していきます。
