AtCoder が提供しているABC（AtCoder Beginner Contest）371 C問題をC++とPythonで解いてみました。ABC371は、2024年9月14日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Make Isomorphic（Difficulty : 849）
問題の詳細は、リンク先をご覧ください。
グラフの頂点の変換を順列全探索します。AtCoder Problems による Difficulty は 849 でした。
解答案
とても難しい問題に見えます。ただし、頂点の数 $N$ は、$1 \leqq N \leqq 8$ と制約が小さいです。この制約から、グラフ $G$ のすべての頂点をグラフ $H$ の頂点に変換する通り数は、$8! = 40320$ となります。また、グラフの辺は、最大でも $(8 \times 7) / 2 = 28$ 個しかありません。
グラフ $G$ の最大 $40320$ 通りの変換したグラフについて、グラフ $H$ と一致していない辺についてコストを計算して、その最小値を求めます。
C++ プログラム例（ABC371C）
プログラムを補足します。
- グラフ $G$ の辺を頂点の2次元 Bool 配列で表現します（12ー20行目）。
- 同じようにグラフ $H$ の辺を頂点の2次元 Bool 配列で表現します（23ー31行目）。
- 辺のコストは、
a[i][j]とa[j][i]で同じ値を設定します（36行目）。 - 標準ライブラリの
next_permutationを用いて、$N$ 次元の順列をすべて生成します。- 変換したグラフ $G$ とグラフ $H$ の頂点の組 $(i, j) \; 1 \leqq i \leqq N, \; i < j \leqq N$ について、差があれば、コストを加えます（49、50行目）。
- 変数
resultをコストの最小値で更新します。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
#define INF (1 << 30)
int main()
{
int n;
cin >> n;
int mg;
cin >> mg;
vector<vector<bool>> edge_G(n, vector<bool>(n, false));
for (int i = 0; i < mg; ++i) {
int u, v;
cin >> u >> v;
--u;
--v;
edge_G[u][v] = true;
edge_G[v][u] = true;
}
int mh;
cin >> mh;
vector<vector<bool>> edge_H(n, vector<bool>(n, false));
for (int i = 0; i < mh; ++i) {
int a, b;
cin >> a >> b;
--a;
--b;
edge_H[a][b] = true;
edge_H[b][a] = true;
}
vector<vector<int>> a(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
cin >> a[i][j];
a[j][i] = a[i][j];
}
}
int result = INF;
vector<int> p(n);
for (int i = 0; i < n; ++i) {
p[i] = i;
}
do {
int cost = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (edge_G[p[i]][p[j]] != edge_H[i][j]) {
cost += a[i][j];
}
}
}
result = min(result, cost);
} while (next_permutation(p.begin(), p.end()));
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC371C）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 371 C"""
import itertools
INF = 1 << 30
n = int(input())
mg = int(input())
edge_G = [[False for _ in range(n)] for _ in range(n)]
for i in range(mg):
u, v = map(int, input().split())
u -= 1
v -= 1
edge_G[u][v] = True
edge_G[v][u] = True
mh = int(input())
edge_H = [[False for _ in range(n)] for _ in range(n)]
for i in range(mh):
a, b = map(int, input().split())
a -= 1
b -= 1
edge_H[a][b] = True
edge_H[b][a] = True
a = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n - 1):
t = list(map(int, input().split()))
index = 0
for j in range(i + 1, n):
a[i][j] = t[index]
index += 1
a[j][i] = a[i][j]
result = INF
for p in list(itertools.permutations(list(range(n)))):
cost = 0
for i in range(n):
for j in range(i + 1, n):
if edge_G[p[i]][p[j]] != edge_H[i][j]:
cost += a[i][j]
result = min(result, cost)
print(result)こちらも「AC」と判定されました。
最後に
制約から順列を使うことが予想できました。制約からアルゴリズムを推測することは本質的な解き方ではありませんが、場合により参考になります。
引き続き ABC の問題を紹介していきます。
