AtCoder が提供しているABC（AtCoder Beginner Contest）328 のE問題をC++で解いてみました。ABC328は、2023年11月11日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Modulo MST（Difficulty : 1160）
問題はリンク先をご覧ください。
すべての辺から頂点数-1個の辺を取り出して調べます。AtCoder Problems による Difficulty は 1160 でした。
解答案
頂点数 $N$ の制約は、$2 \leqq N \leqq 8$ となっています。仮に $N=8$ の場合、グラフにあり得る辺は、$_8C_2 = 8 \times 7 / 2 = 28$ 個となります。グラフが全域木になるために辺の数は、$N-1=7$ 個である必要があります。このため、あり得る28個の辺から、7個の辺を選ぶ場合の数は、以下となります。
$$_{28}C_7 = \frac{28 \times 27 \times \cdots \times 22}{7 \times 6 \times \cdots \times 1} = 1184040 \doteqdot 10^6$$
選択した7個の辺でグラフ全体が連結している場合に、重さの総和の K による剰余を計算した後の最小値を求めます。
C++ プログラム例（ABC328E）
プログラムについてのコメントです。
- m 個の辺から n-1 個の辺を取るための順列 p を用意します（20ー26行目）。
- next_permutation を使って、n-1個の辺を取り出します。具体的には、p[i] の値が 0 の辺を取り出します。
- 取り出した辺が以下を満たすか確認します。
- 取り出した辺が新しい頂点とつないでいる（UnionFindで同じグラフに所属していないことを確認する）。ACL の UnionFind を使いました（2、4行目）。
- n-1個の辺がすべて上記を満たせば、全体として連結しています。このとき、t_result の k による剰余を計算して、最小値 result を更新します（44、45行目）。
- 最小値 result を出力する。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
typedef long long int ll;
#define INF (1ULL << 60)
int main()
{
int n, m;
ll k;
cin >> n >> m >> k;
vector<int> u(m), v(m);
vector<ll> w(m);
for (int i = 0; i < m; ++i) {
cin >> u[i] >> v[i] >> w[i];
}
vector<int> p(m);
for (int i = 0; i < n - 1; ++i) {
p[i] = 0;
}
for (int i = n - 1; i < m; ++i) {
p[i] = 1;
}
ll result = INF;
do {
dsu uf(n + 1);
ll t_result = 0;
bool t_ok = true;
for (int i = 0; i < m; ++i) {
if (p[i] == 0) {
if (!uf.same(u[i], v[i])) {
uf.merge(u[i], v[i]);
t_result += w[i];
} else {
t_ok = false;
break;
}
}
}
if (t_ok) {
result = min(result, t_result % k);
}
} while (next_permutation(p.begin(), p.end()));
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python の UnionFind と順列について
Python は、UnionFind を標準ライブラリとしては用意していません（私の実装はABC304E問題の解説記事で紹介しました）。また、順列生成（itertools.permutations）は同じ文字を区別しません（ABC326D問題でも解説しました）。
Python 版は、なるべく言語標準のライブラリで実装したいと考えています。このような事情で、この記事では、Python に移植したプログラムの紹介を省略します。
最後に
コンテストでは、全域木の定義を勘違いしていました。辺が $N-1$ 個より多い場合も探索範囲に入れていました。その結果、実装ができませんでした。※よく考えれば、辺が $N-1$ 個より多ければ、そもそも「木」になりません。
公式解説を読み理解して、自分なりに実装したプログラムを紹介しました。
引き続き ABC の問題を紹介していきます。
