AtCoder が提供しているABC（AtCoder Beginner Contest）324 のF問題をC++とPythonで解いてみました。ABC324は、2023年10月14日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 Beautiful Path（Difficulty : 1815）
問題はリンク先をご覧ください。
求める最大値を値の二分探索で求めます。判定関数でDPを使います。AtCoder Problems による Difficulty は、1815 でした。
解答案
最大値を解の二分探索で求めます。具体的には、$P$ 上のすべての辺の美しさの総和を、$P$ 上のすべての辺のコストの総和で割った値が $X$ 以上になるか判定する関数 is_OK の結果から値を絞り込んでいきます。1回の呼び出しで値の範囲が半分になります。100回繰り返すと $2^{100} \doteqdot 10^{30}$ となり、10進数30桁の精度となります。
関数 is_OK の実装を考えます。頂点$1$から頂点$N$の辺のパスを $i_1, \dots, i_m$ とすると、判定式は以下となります。
$$\frac{\sum_{k=1}^m b_{ik}}{\sum_{k=1}^m c_{ik}} \geqq X$$
この式は以下のように書き換えます。
$$\sum_{k=1}^m b_{ik} \geqq \sum_{k=1}^m c_{ik} X, \; \sum_{k=1}^m (b_{ik} – c_{ik} X) \geqq 0$$
各辺の重みを $b_i – c_i X$ として、辺の和が 0 以上か判定します。グラフの辺は、制約から小さい頂点から大きい頂点に向かうため、以下の漸化式によって求めることができます。
dp[vi] = max(dp[vi], dp[ui] + bi – ci X)
辺 ui → vi を、ui が小さい方から処理することにより計算量 $O(M)$ により、dp[N] を求めることができます。この漸化式の考え方は、ABC309E問題（解説）と同じです。
C++ プログラム例（ABC324F）
上記の考察を実装します。
- 読み取った辺は、ui とインデックスを合わせて小さい順にソートしておきます（35行目）。
- 解の二分探索を求めるコードは定番となります（37ー49行目）。
- 判定関数 is_OK で、DP を用いて判定を行います（10ー21行目）。
- 浮動小数点数は printf で出力しました（51行目）。
以下は、C++のプログラムです。
#include <bits/stdc++.h>
using namespace std;
#define INF (1ULL << 60)
int n, m;
vector<pair<int, int>> u;
vector<int> v, b, c;
bool is_OK(double mid)
{
vector<double> dp(n + 1, -1.0 * INF);
dp[1] = 0.0;
for (int i = 0; i < m; ++i) {
int ut = u[i].first;
int index = u[i].second;
dp[v[index]] = max(dp[v[index]], dp[ut] + b[index] - mid * c[index]);
}
return dp[n] >= 0.0;
}
int main()
{
cin >> n >> m;
u.resize(m);
v.resize(m);
b.resize(m);
c.resize(m);
for (int i = 0; i < m; ++i) {
int t;
cin >> t >> v[i] >> b[i] >> c[i];
u[i] = make_pair(t, i);
}
sort(u.begin(), u.end());
double ng = 10001.0;;
double ok = 0.0;
int count = 0;
while (count < 100) {
++count;
double mid = (ok + ng) / 2.0;
if (is_OK(mid)) {
ok = mid;
} else {
ng = mid;
}
}
printf("%.16lf\n", ok);
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC324F）
基本的な考え方は同じです。浮動小数点数は、f文字列で出力しています（43行目）。以下となります。
"""AtCoder Beginner Contest 324 F"""
INF = 1 << 60
def is_OK(mid):
global n, m, u, v, b, c
dp = [-1.0 * INF] * (n + 1)
dp[1] = 0.0
for i in range(m):
ut = u[i][0]
index = u[i][1]
dp[v[index]] = max(dp[v[index]],
dp[ut] + b[index] - mid * c[index])
return dp[n] >= 0.0
n, m = map(int, input().split())
u = [(0, 0)] * m
v = [0] * m
b = [0] * m
c = [0] * m
for i in range(m):
t, v[i], b[i], c[i] = map(int, input().split())
u[i] = (t, i)
u.sort()
ng = 10001.0
ok = 0.0
count = 0
while count < 100:
count += 1
mid = (ok + ng) / 2.0
if is_OK(mid):
ok = mid
else:
ng = mid
print(f"{ok:.16f}")こちらも「AC」と判定されました。
最後に
この問題は、大きな枠組みは「浮動小数点数の解の二分探索」です。判定関数には、「小さい頂点から決まってくるDP」を使って解くことができました。
公式解説を参考にしながらではありますが、わたしにとって難易度が高い問題を解くことができました。
引き続き ABC の問題を紹介していきます。
