AtCoder が提供しているABC（AtCoder Beginner Contest）270 のF問題をC++で解いてみました。ABC270は、2022年9月24日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 Transportation（Difficulty : 1834）
問題はリンク先をご覧ください。
空港と港のそれぞれの有無で4通りの最小全域木を作ります。AtCoder Problems による Difficulty は、1834 でした。
解答案
仮に空港も港もないとすると、道路だけを使った最小全域木の問題となります。クラスカル法を用いるとコストが小さい方から、UnionFind で統合していくだけです。
空港を作って飛行機を使う場合は、空を仮の頂点として設定すると同じことができます。港を作って船を使う場合は、海を仮の頂点として設定すると同じことができます。空港と港の有無で4つの最小全域木が構築できますが、そのコストの最小値が解答となります。
C++ プログラム例（ABC270F）
空港と港の有無を0から3までのビット表現でループさせます（bit全探索）。それぞれの場合で、頂点数（v_size）と辺のコスト（cost）を設定します（29ー46行目）。
- 空港を作る場合、頂点N＋１を空と考えます。
- 港を作る場合、頂点N+2を海と考えます。
コストが小さい方から、UnionFind を使って頂点を統合していきます（48ー60行目）。統合した頂点数と頂点数が一致する場合に、最小値を更新します（63行目）。
以下が、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;
cin >> n >> m;
vector<ll> x(n);
for (int i = 0; i < n; ++i) {
cin >> x[i];
}
vector<ll> y(n);
for (int i = 0; i < n; ++i) {
cin >> y[i];
}
vector<int> a(m), b(m);
vector<ll> z(m);
for (int i = 0; i < m; ++i) {
cin >> a[i] >> b[i] >> z[i];
}
ll result = INF;
for (int bit = 0; bit < 4; ++bit) {
int v_size = n;
vector<pair<ll, pair<int, int>>> cost;
if ((bit & 1) != 0) {
++v_size;
for (int i = 0; i < n; ++i) {
cost.push_back(make_pair(x[i], make_pair(i + 1, n + 1)));
}
}
if ((bit & 2) != 0) {
++v_size;
for (int i = 0; i < n; ++i) {
cost.push_back(make_pair(y[i], make_pair(i + 1, n + 2)));
}
}
for (int i = 0; i < m; ++i) {
cost.push_back(make_pair(z[i], make_pair(a[i], b[i])));
}
sort(cost.begin(), cost.end());
dsu uf(n + 3);
ll this_result = 0;
ll this_size = 1;
for (int i = 0; i < cost.size(); ++i) {
ll c = cost[i].first;
int n1 = cost[i].second.first;
int n2 = cost[i].second.second;
if (!uf.same(n1, n2)) {
uf.merge(n1, n2);
this_result += c;
++this_size;
}
}
if (this_size == v_size) {
result = min(result, this_result);
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python は、標準ライブラリで UnionFind が用意されていないため、プログラムの紹介を省略します。
最後に
ABC270のコンテスト時は、ＡとＢ問題の2問しか解けませんでした。Ｆ問題は問題を読むことさえできませんでした。
この問題は、青Difficultyでした。以下の要素を組み合わせています。
このレベルの問題が、本番コンテストで解ければと思います。
引き続き ABC の問題を紹介していきます。
