AtCoder が提供しているABC（AtCoder Beginner Contest）374 D問題をC++で解いてみました。ABC374は、2024年10月5日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Laser Marking（Difficulty : 694）
問題の詳細は、リンク先をご覧ください。
再帰関数で全検索しました。AtCoder Problems による Difficulty は 694 でした。
解答案
$1 \leqq N \leqq 6$ と制約が小さいため、線分を選ぶすべての順列（$6!$）に対して、端を選ぶ $2^6$ 通りを掛けても $6! \times 2^6 = 46080$ 通りであるため、全検索しても十分に間に合います。
C++ プログラム例（ABC374D）
再帰関数で実装しました。
- 再帰関数 rec の引数は、いま選んでいる線分 i、方向 direction、今までの時間の累計 dist です。
- 最初に線分を選び、両端に対して再起関数 rec を呼びます（65、66行目）。
- 再帰関数 rec で以下を計算します。
- 選択した線分の長さを照射する時間を求めます（14－15行目）。
- もしすべての線分が選択されていたら、その時間の累計が最小値となっているか確認します（16ー22行目）。
- まだ選択されていない線分があれば、その線分を選び、両端に対して再起関数 rec を呼びます（33ー51行目）。
以下が、C++プログラムです。一部の長い行は折り返しています。
#include <bits/stdc++.h>
using namespace std;
#define INF (double)(1LL << 60)
int n;
double s, t;
vector<int> a(6), b(6), c(6), d(6);
vector<bool> used(6, false);
double result = INF;
void rec(int i, int direction, double dist)
{
dist +=
sqrt((a[i] - c[i]) * (a[i] - c[i]) + (b[i] - d[i]) * (b[i] - d[i])) / t;
bool is_full = true;
for (int j = 0; j < n; ++j) {
if (!used[j]) {
is_full = false;
break;
}
}
if (is_full) {
result = min(result, dist);
return;
}
for (int j = 0; j < n; ++j) {
if (used[j]) {
continue;
}
used[j] = true;
if (direction == 0) {
rec(j, 0,
dist + sqrt((c[i] - a[j]) * (c[i] - a[j]) +
(d[i] - b[j]) * (d[i] - b[j])) /
s);
rec(j, 1,
dist + sqrt((c[i] - c[j]) * (c[i] - c[j]) +
(d[i] - d[j]) * (d[i] - d[j])) /
s);
} else {
rec(j, 0,
dist + sqrt((a[i] - a[j]) * (a[i] - a[j]) +
(b[i] - b[j]) * (b[i] - b[j])) /
s);
rec(j, 1,
dist + sqrt((a[i] - c[j]) * (a[i] - c[j]) +
(b[i] - d[j]) * (b[i] - d[j])) /
s);
}
used[j] = false;
}
}
int main()
{
cin >> n >> s >> t;
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
}
for (int i = 0; i < n; ++i) {
used[i] = true;
rec(i, 0, sqrt(a[i] * a[i] + b[i] * b[i]) / s);
rec(i, 1, sqrt(c[i] * c[i] + d[i] * d[i]) / s);
used[i] = false;
}
cout << fixed << setprecision(12);
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
今回は、Python プログラムの紹介は見送ります。
最後に
再帰関数にも慣れてきました。
引き続き ABC の問題を紹介していきます。
