I - Beautiful Path 解説 by MMNMM

誤差のない値を得る方法

この問題の答えは、既約分数として表したときに分母および分子がたかだか \(2\times10 ^ 9\) であるような有理数として表すことができます。 この有理数の分子と分母の値を整数として得る方法について考えます。

まず、実数の二分探索を用いて問題が解ける（つまり、実数に対して解との大小を求められる）場合、有理数との大小を適切に実装することができればこの解説と同様の方法でこの問題の真の解を得ることができます。

また、この問題は Dinkelbach algorithm と呼ばれるアルゴリズムで解くこともできます。

この問題は、\(\displaystyle f(t)=\max _ {P\in S _ P}(B(P)-tC(P))\) とすると \(f(t)=0\) となる \(t\) を求める問題に帰着されます。

説明

ある正実数 \(t\) について解が \(t\) 以下であるということは、頂点 \(1\) から頂点 \(N\) までのパス全体の集合を \(S _ P\) として、\(B(P)\coloneqq \) パス \(P\) に含まれる辺の美しさの合計 および \(C(P)\coloneqq \) パス \(P\) に含まれる辺のコストの合計 について、次が成り立つことです。

\[\max _ {P\in S _ P}\dfrac{B(P)}{C(P)}\leq t\]

これを変形すると、

\[\begin{aligned} &\max _ {P\in S _ P}\dfrac{B(P)}{C(P)}\leq t\\ \iff&{} ^ \forall P\in S _ P.\,\dfrac{B(P)}{C(P)}\leq t\\ \iff&{} ^ \forall P\in S _ P.\,B(P)\leq tC(P)\qquad(\because 1\leq c _ i)\\ \iff&{} ^ \forall P\in S _ P.\,B(P)-tC(P)\leq0\\ \iff&\max _ {P\in S _ P}(B(P)-tC(P))\leq0 \end{aligned}\]

となります。

ここで、\(t\) を定めるごとに \(f(t)\) を与える \(P\) を得ることができます。 これを \(P _ t\) と書くことにします。

Dinkelbach algorithm は、\(t\) を適切な初期値にとり、\(t\leftarrow\dfrac{B(P _ t)}{C(P _ t)}\) で更新することを繰り返すことによって \(f(t)=0\) となる \(t\) を求める手法です（これは、\(f(t)\) の零点を近似するために Newton 法を用いていると見ることもできます）。

この問題の設定（を含む条件）のもとで、Dinkelbach algorithm は有限回の繰り返しで \(f(t)=0\) なる \(t\) に収束することが示されています。 この問題で用いられたテストケースでは、たかだか \(5\) 回の繰り返しで収束することが確かめられます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <ranges>
#include <limits>
#include <iomanip>

int main() {
    using namespace std;
    
    unsigned N, M;
    cin >> N >> M;
    vector<vector<tuple<unsigned, unsigned, unsigned>>> edges(N);
    for (unsigned u, v, b, c; [[maybe_unused]] const auto _ : views::iota(0U, M)) {
        cin >> u >> v >> b >> c;
        edges[--u].emplace_back(--v, b, c);
    }

    // dp[i] := 頂点 i に到達するための (合計美しさ, 合計コスト) の中で 合計美しさ * y - 合計コスト * x が最大のもの
    vector<pair<unsigned long, unsigned long>> dp(N, {0, numeric_limits<unsigned>::max()});
    dp[0] = {0, 0};

    // 配る DP で B(P_t) / C(P_t) を求める
    const auto iteration{[N, &edges, &dp](unsigned long x, unsigned long y) -> pair<unsigned long, unsigned long>& {
        for (const auto u : views::iota(0UL, N))
            for (const auto&[u_b, u_c]{dp[u]}; const auto&[v, b, c] : edges[u])
                if (dp[v].first * y + (u_c + c) * x < (u_b + b) * y + dp[v].second * x) // より大きければ更新
                    dp[v] = {u_b + b, u_c + c};
        return dp.back();
    }};

    pair<unsigned long, unsigned long> t{1, 0}, prev{};
    auto&&[x, y]{t};
    do
        swap(t, prev = iteration(x, y));
    while (t != prev); // 収束したらループを抜ける
    
    cout << fixed << setprecision(10) << static_cast<long double>(x) / y << endl;
    
    return 0;
}

投稿日時:
最終更新: