AtCoder が提供しているABC（AtCoder Beginner Contest）274 のE問題をC++とPythonで解いてみました。ABC274は、2022年10月22日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Booster（Difficulty : 1520）
問題はリンク先をご覧ください。
巡回セールスマン問題の応用です。AtCoder Problems による Difficulty は、1520 でした。
解答案
巡回セールスマン問題の紹介
昨日の記事で、以下の巡回セールスマン問題について紹介しました。
- 都市の集合と2都市間の移動コストが与えられる。
- 全ての都市をちょうど一度ずつ訪れて出発地に戻る閉路のうちで、総移動コストが最小のものを求める。
記事でも紹介したキーとなるコードを示します。コードにある dist[j][k] は、都市jから都市kの移動コストを表します。
vector<vector<int>> dp((1 << n), vector<int>(n, INF));
dp[0][0] = 0;
for (int i = 0; i < (1 << n); ++i) {
for (int j = 0; j < n; ++j) {
if (((i & (1 << j)) == 0)&&(i != 0)) {
continue;
}
for (int k = 0; k < n; ++k) {
if ((i & (1 << k)) == 0) {
int v = (i | (1 << k));
dp[v][k] = min(dp[v][k], dp[i][j] + dist[j][k]);
}
}
}
}C++ プログラム例（ABC274E）
巡回セールスマン問題と比較した点を列挙します。距離を表す配列 dist と dp を double 型に変更しています。
- 原点とN個の街とM個の宝箱を同じように扱います。
- 原点は街のひとつとして扱う。読み込んだNをインクリメントしておく（10行目）。
- 集合は、（N＋M）ビットとして扱う。下位Nビットを街とする。上位Mビットを宝箱とする。
- 巡回セールスマン問題と同様の処理をします。
- 訪れた宝箱の個数によって移動時間が変わる。
- 宝箱Mビットがセットされている個数によって、2.0で割る個数を増やす配列 div を前準備として計算しておく（26ー35行目）。
- 下位Nビットがすべてセットされている index について、dp[index][0]の最小値が解となる（53ー58行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
#define INF (1ULL << 60)
int main()
{
int n, m;
cin >> n >> m;
++n;
vector<double> x(n + m), y(n + m);
x[0] = 0.0;
y[0] = 0.0;
for (int i = 1; i < n + m; ++i) {
cin >> x[i] >> y[i];
}
vector<vector<double>> dist(n + m, vector<double>(n + m));
for (int i = 0; i < n + m; ++i) {
for (int j = 0; j < n + m; ++j) {
dist[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j])
+ (y[i] - y[j]) * (y[i] - y[j]));
}
}
vector<double> div(1 << m);
for (int i = 0; i < (1 << m); ++i) {
double d = 1.0;
for (int j = 0; j < m; ++j) {
if ((i & (1 << j)) != 0) {
d *= 2.0;
}
}
div[i] = d;
}
vector<vector<double>> dp(1 << (n + m), vector<double>((n + m), (double)INF));
dp[0][0] = 0.0;
for (int i = 0; i < (1 << (n + m)); ++i) {
for (int j = 0; j < (n + m); ++j) {
if (((i & (1 << j)) == 0)&&(i != 0)) {
continue;
}
for (int k = 0; k < (n + m); ++k) {
if ((i & (1 << k)) == 0) {
int v = (i | (1 << k));
dp[v][k] = min(dp[v][k], dp[i][j] + dist[j][k] / div[i >> n]);
}
}
}
}
double result = (double)INF;
for (int i = 0; i < (1 << m); ++i) {
unsigned index = (1 << n) - 1;
index += (i << n);
result = min(result, dp[index][0]);
}
cout << fixed << setprecision(10);
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC274E）
Python 版も基本的な考え方は同じです。浮動小数点数は、f文字列で出力しています（16行目）。
以下のプログラムは、「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。
"""AtCoder Beginner Contest 274 E"""
INF = float(1 << 60)
n, m = map(int, input().split())
n += 1
x = [0.0] * (n + m)
y = [0.0] * (n + m)
for i in range(1, n + m):
x[i], y[i] = map(float, input().split())
dist = [[0.0 for _ in range(n + m)] for _ in range(n + m)]
for i in range(n + m):
for j in range(n + m):
dist[i][j] = ((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2) ** 0.5
div = [0.0] * (1 << m)
for i in range(1 << m):
d = 1.0
for j in range(m):
if (i & (1 << j)) != 0:
d *= 2.0
div[i] = d
dp = [[INF for _ in range(n + m)] for _ in range(1 << (n + m))]
dp[0][0] = 0.0
for i in range(1 << (n + m)):
for j in range(n + m):
if (i & (1 << j) == 0) and i != 0:
continue
for k in range(n + m):
if (i & (1 << k)) == 0:
v = i | (1 << k)
dp[v][k] = min(dp[v][k], dp[i][j] + dist[j][k] / div[i >> n])
result = INF
for i in range(1 << m):
index = (1 << n) - 1
index += (i << n)
result = min(result, dp[index][0])
print(f"{result:.10f}")こちらも「AC」と判定されました。
最後に
1年以上前に挑戦したときは、まったく解けませんでした。解きなおして、実装はやや重いものの典型的な問題の応用となっていることが分かりました。解けるメニューをすこしずつ増やしていく楽しみがあります。
引き続き ABC の問題を紹介していきます。
