AtCoder ABC 324 F - Beautiful Path (青色, 500 点)

とても教育的問題！！　蟻本の二分探索の節に「平均値の最大化」があるけど、まさにそれ！！！

• 問題へのリンク

問題概要

頂点数 、辺数 の DAG が与えられる。各辺 について、 であることが保証される。

各辺 には、美しさ と、コスト がついている。

頂点 0 から頂点 へと至るパスのうち、美しさの総和 / コストの総和として考えられる最大値を求めよ。

制約

• 

考えたこと

これは「平均値の最大化」である。コストを重みと捉えれば、パスに含まれる各辺の重み付き平均値を最大化したい問題だと言える。

平均値の最大化を二分探索に帰着させるのは中堅典型だが、結構忘れられがちな気がする。とても教育的な問題だと思う！！

求める解を 以上にできるかどうかを問う問題を考えよう。簡単のため、パスが 3 辺からなるとして、それぞれ美しさが 、コストが であるとしたとき、条件は

⇔

と同値変形できる。よって、3 辺に限らず一般の場合であっても、

---

頂点 0 から頂点 へと至るパスであって、各辺 についての の総和が 0 以上であるものが存在するかどうかを判定せよ

---

という問題を解けば良いことがわかる。これは DAG 上の最長路問題であって、DP で解ける。

計算量は、二分探索のイテレーション回数を としたとき、 と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using pint = pair<int, int>;
using pll = pair<long long, long long>;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl


struct Edge {
    int to;
    double b, c;
    Edge() {}
    Edge(int to, double b, double c) : to(to), b(b), c(c) {}
};
using Graph = vector<vector<Edge>>;

double INF = 1LL<<50;
int main() {
    int N, M;
    cin >> N >> M;
    
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        double b, c;
        cin >> u >> v >> b >> c;
        --u, --v;
        G[u].push_back(Edge(v, b, c));
    }
    
    double low = 0, high = INF;
    for (int _ = 0; _ < 100; ++_) {
        double x = (low + high) / 2;
        
        // 各パスの b[i] - x c[i] の総和を 0 以上にできるかどうかを判定する
        // つまり、各辺のコストを b[i] - x c[i] としたときの最長路が 0 以上かどうかを判定する
        vector<double> dp(N, -INF);
        dp[0] = 0;
        for (int v = 0; v < N; ++v) {
            for (auto e : G[v]) {
                chmax(dp[e.to], dp[v] + (e.b - x * e.c));
            }
        }
        if (dp[N-1] >= 0) low = x;
        else high = x;
    }
    cout << fixed << setprecision(10) << low << endl;
}