AtCoder が提供しているABC（AtCoder Beginner Contest）282 のE問題をC++で解いてみました。ABC282は、2022年12月17日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Choose Two and Eat One（Difficulty : 1604）
問題はリンク先をご覧ください。
ABC282 E問題 Choose Two and Eat One
グラフの問題と考えて、最大全域木を構築します。AtCoder Problems による Difficulty は、1604 でした。
考察
最小全域木とは
最小全域木については、「典型アルゴリズム問題集」のF問題で紹介していました。簡単に説明すると、最小全域木は以下のようなグラフです。
- すべての頂点が連結となるように辺が設定されている。
- 辺の重みが最小となる辺の張り方となっている。
- 結果的に、グラフに含まれる辺の数は、（頂点-1）個となる。グラフは木になる。
最小全域木を求める方法として、上記の記事でクラスカル法を紹介しています。UnionFind を使って、まだ統合されていない頂点の辺をコストが小さい方から統合していきます。大きい方から統合すると最大全域木が得られます。
解答案
C++ プログラム例（ABC282E）
最小全域木と最大全域木は、辺のコストが小さい方から設定するか、大きい方から設定するかの違いしかありません（クラスカル法）。
プログラムの説明を補足します。
- $x^y \bmod m$ を求めるために自作関数 power を使います（8ー18行目）。
- 頂点の間の辺のコストを配列 point に格納して、大きい順にソートします（39行目）。
- UnionFind は、ACL（AtCoder Library）を使いました。コストが大きい順番にグラフを統合していきます（41ー51行目）。
- 設定した辺のコストの合計を出力します（53行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
typedef unsigned long long int ull;
ull power(ull n, ull p, ull mod)
{
if (p == 0) {
return 1;
}
if (p % 2 == 0) {
ull t = power(n, p / 2, mod);
return t * t % mod;
}
return (n * power(n, p - 1, mod))% mod;
}
int main()
{
int n;
ull m;
cin >> n >> m;
vector<ull> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<pair<ull, pair<int, int>>> point;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
ull t = power(a[i], a[j], m);
t += power(a[j], a[i], m);
t %= m;
point.push_back(make_pair(t, make_pair(i, j)));
}
}
sort(point.begin(), point.end(), greater<pair<ull, pair<int, int>>>());
ull result = 0;
dsu uf(n);
for (int i = 0; i < point.size(); ++i) {
ull cost = point[i].first;
int n1 = point[i].second.first;
int n2 = point[i].second.second;
if (!uf.same(n1, n2)) {
uf.merge(n1, n2);
result += cost;
}
}
cout << result << endl;
return 0;
}コストにマイナスを掛けると、最小全域木となります。一部の変数の型を unsigned long long から long long に変更しています。以下となります。
#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
typedef unsigned long long int ull;
typedef long long int ll;
ull power(ull n, ull p, ull mod)
{
if (p == 0) {
return 1;
}
if (p % 2 == 0) {
ull t = power(n, p / 2, mod);
return t * t % mod;
}
return (n * power(n, p - 1, mod))% mod;
}
int main()
{
int n;
ull m;
cin >> n >> m;
vector<ll> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<pair<ll, pair<int, int>>> point;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
ll t = (ll)power(a[i], a[j], m);
t += (ll)power(a[j], a[i], m);
t %= m;
point.push_back(make_pair(-t, make_pair(i, j)));
}
}
sort(point.begin(), point.end());
ll result = 0;
dsu uf(n);
for (int i = 0; i < point.size(); ++i) {
ll cost = -point[i].first;
int n1 = point[i].second.first;
int n2 = point[i].second.second;
if (!uf.same(n1, n2)) {
uf.merge(n1, n2);
result += cost;
}
}
cout << result << endl;
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python は、標準ライブラリで UnionFind が用意されていないため、プログラムの紹介を省略します。
最後に
ABC282のコンテスト時は、E問題はまったく歯が立ちませんでした。当時のコメントに「問題を読んであきらめる」とありました。
最小全域木のことは、学んではいましたが使うような問題を解いていませんでした。今回、解説を読んで、実際に問題を解くことによって理解が含まったと考えています。
引き続き ABC の問題を紹介していきます。
