$d$-edge Shortest Path on Monge Graph
(src/optimization/monge_d_edge_shortest_path.hpp)

• View this file on GitHub
• Last update: 2024-06-01 01:35:37+09:00
• Include: #include "src/optimization/monge_d_edge_shortest_path.hpp"

概要

完全 DAG $G(V, E)\ (|V| = N + 1)$ について，その辺重み $c : E \to \mathbb{Z}$ が monge 性を満たす際に頂点 $0$ から各点までの最短路長を $\mathrm{O}(N \log N)$ で，辺を丁度 $D$ 本使う $0$ から $N - 1$ への最短路長を $\mathrm{O}(N \log N \log \max_{e \in E} |c(e)|)$ で求める．

LARSCH algorithm を用いることでそれぞれ $\log N$ を落とすことが可能．

Links

• Monge グラフ上の $d$-辺最短路長を計算するアルゴリズム | Kyopro Encyclopedia of Algorithms
• Aliens DP で辺の本数が区間で指定される場合 - noshi91のメモ
• Incredibly beautiful DP optimization from $N^3$ to $N \log^2 N$ - Codeforces
• Monge の手引書 (tatyam)
• https://twitter.com/noshi91/status/1625587844000649217

問題例

• AtCoder Beginner Contest 218 H - Red and Blue Lamps
• The 1st Universal Cup. Stage 3: Poland I. Investors
• 東北大学プログラミングコンテスト 2022 K - Lebesgue Integral
• AtCoder Beginner Contest 305 Ex - Shojin

Depends on

• Golden Section Search (src/optimization/golden_section_search.hpp)

Code

#include <cassert>
#include <functional>
#include <limits>
#include <vector>
#include "golden_section_search.hpp"

template <typename T> std::vector<T> monge_shortest_path(int N, const std::function<T(int, int)>& f) {
    std::vector<T> dp(N + 1, std::numeric_limits<T>::max() / 2);
    std::vector<int> x(N + 1);
    dp[0] = x[0] = 0, x[N] = N;
    auto check = [&](int from, int to) {
        if (from >= to) return;
        T cost = f(from, to);
        if (dp[from] + cost < dp[to]) {
            dp[to] = dp[from] + cost;
            x[to] = from;
        }
    };
    auto solve = [&](auto&& self, int l, int r) -> void {
        if (l >= r) return;
        int m = (l + r) >> 1;
        x[m] = x[l];
        for (int i = x[l]; i <= x[r]; i++) check(i, m);
        if (r - l > 1) self(self, l, m);
        for (int i = l; i <= m; i++) check(i, r);
        if (r - l > 1) self(self, m, r);
    };
    solve(solve, 0, N);
    return dp;
}

long long monge_d_edge_shortest_path(int N, int D, long long upper, const std::function<long long(int, int)>& f) {
    assert(0 <= upper);
    auto dp = [&](long long x) -> long long {
        auto g = [&](int from, int to) -> long long { return f(from, to) + x; };
        long long cost = monge_shortest_path<long long>(N, g)[N];
        return cost - 1LL * D * x;
    };
    auto [tmp, res] = golden_section_search<long long, false>(dp, -upper, upper);
    return res;
}

#line 1 "src/optimization/monge_d_edge_shortest_path.hpp"
#include <cassert>
#include <functional>
#include <limits>
#include <vector>
#line 3 "src/optimization/golden_section_search.hpp"
#include <utility>

template <typename T, bool get_min = true>
std::pair<long long, T> golden_section_search(const std::function<T(long long)>& f, long long mini, long long maxi) {
    assert(mini <= maxi);
    long long a = mini - 1, x, b;
    {
        long long s = 1, t = 2;
        while (t < maxi - mini + 2) std::swap(s += t, t);
        x = a + t - s, b = a + t;
    }
    T fx = f(x), fy;
    while (a + b != 2 * x) {
        long long y = a + b - x;
        fy = f(y);
        if (maxi < y or (get_min ? fx < fy : fx > fy)) {
            b = a;
            a = y;
        } else {
            a = x;
            x = y;
            fx = fy;
        }
    }
    return {x, fx};
}
#line 6 "src/optimization/monge_d_edge_shortest_path.hpp"

template <typename T> std::vector<T> monge_shortest_path(int N, const std::function<T(int, int)>& f) {
    std::vector<T> dp(N + 1, std::numeric_limits<T>::max() / 2);
    std::vector<int> x(N + 1);
    dp[0] = x[0] = 0, x[N] = N;
    auto check = [&](int from, int to) {
        if (from >= to) return;
        T cost = f(from, to);
        if (dp[from] + cost < dp[to]) {
            dp[to] = dp[from] + cost;
            x[to] = from;
        }
    };
    auto solve = [&](auto&& self, int l, int r) -> void {
        if (l >= r) return;
        int m = (l + r) >> 1;
        x[m] = x[l];
        for (int i = x[l]; i <= x[r]; i++) check(i, m);
        if (r - l > 1) self(self, l, m);
        for (int i = l; i <= m; i++) check(i, r);
        if (r - l > 1) self(self, m, r);
    };
    solve(solve, 0, N);
    return dp;
}

long long monge_d_edge_shortest_path(int N, int D, long long upper, const std::function<long long(int, int)>& f) {
    assert(0 <= upper);
    auto dp = [&](long long x) -> long long {
        auto g = [&](int from, int to) -> long long { return f(from, to) + x; };
        long long cost = monge_shortest_path<long long>(N, g)[N];
        return cost - 1LL * D * x;
    };
    auto [tmp, res] = golden_section_search<long long, false>(dp, -upper, upper);
    return res;
}

Back to top page