2020-12-25

JOI 本選 2014 D - フクロモモンガ (AOJ 0601, 難易度 8)

JOI JOI本選 JOI難易度8 DP DP値を利用して状態復元 Dijkstra法最短路問題体力や燃料がある一定以上必要になる設定の問題グラフ AtCoder AOJ 最適化テク:最適解の形を考える最適化テク:解を変形していく(最適性を失わずに) 最適化テク:固定する変数を入れ替えて考えるある量を固定して考える Greedy:今が良いほど未来も良い Greedy ある量を決めるとGreedy

dp の値そのものを用いて現在状態を復元する系の問題。

問題概要

$N$ 個の木 $1, 2, \dots, N$ があって、それぞれ高さは $H_{1}, \dots, H_{N}$ である。

フクロモモンガは最初は、木 1 の高さ $X$ の地点にいる。フクロモモンガは木を飛び移りながさ、最終的に木 $N$ の頂上にたどり着きたい。

ただし互いに移り渡れる木の組は指定されていて、 $M$ 組ある。その $M$ 組以外の木同士は飛び移れない。 $M$ 組それぞれについて所要時間も与えられる。

さて、フクロモモンガは飛び移るときに $t$ 秒を要するとき、その高さも $t$ だけ減少する。したがって飛び移る直前の高さは $t$ 以上でなければならない。また、飛び移る直線の高さを $h$ としたとき、飛び移る先の木の高さ $H$ が $H \ge h - t$ を満たさなければならない。

また、フクロモモンガは同じ木を上下することができる。高さを 1 だけ増やしたり 1 減らしたりするのに 1 秒を要する。

フクロモモンガが木 $N$ の頂上にたどり着くのに要する最短時間を求めよ。不可能の場合は -1 を出力せよ。

制約

$2 \le N \le 10^{5}$
$1 \le M \le 3 \times 10^{5}$
$1 \le X, H_{i} \le 10^{9}$

考えたこと

一見すると、(木, 高さ) をペアにした Dijkstra 法ではないかと思って途方に暮れてしまう問題。しかし木の個数の時点で $10^{5}$ あるし、高さにいたっては $10^{9}$ 刻みなのでとても無理。

こういうとき、木の高さとして実際には少数の場合だけ考えればよいのではなかという思考の方向性がありうる。しかしそれをしたとしても各木ごとに $O(N)$ 通りくらいの選択肢はありそう。それでは厳しい。

というわけで、フクロモモンガの最適行動パターンを考察してみよう。フクロモモンガの飛び移る木の順序を決めたとき、基本的には次のような戦略で動いて構わない。こういうふうに「最適解の形を考察して決め込む」という考察はとても大事だと思う。ここで、今いる木の高さを $H_{f}$ 、飛び移るのに要する時間を $T$ 、飛び移る先の木の高さを $H_{t}$ とする。

のとき (高すぎる)
- いったん高さを $H_{t} + T$ まで下がる
- その時点で飛び移る、飛び移った先の木の高さは $H_{t}$ となる
- 所要時間は $H_{f} - H_{t}$ と表せる
のとき (低すぎる)
- いったん高さを $T$ まで上がる ( $T \gt H_{f}$ の場合は飛び移り不可)
- その時点で飛び移る、飛び移った先の木の高さは 0 となる
- 所要時間は $2T - H_{f}$ と表せる
のとき (ちょうどいい)
- 直ちに飛び移る、飛び移った先の木の高さは $H_{f} - T$ となる
- 所要時間は $T$ と表せる

このような戦略で行けば、余計な動きはしないで済む。ちゃんと証明しようと思うと面倒だけど、まあ OK。

dp の値から、現在の高さを復元できる！

この戦略に従ったとき、実は次のことがわかる！！！

木 $v$ に到達した時点での最短所要時間が $T$ であったとする
もし $T \lt X$ ならば、木 $v$ の高さ 0 の地点に飛びついたと考えてよい
逆に $T \ge X$ ならば、木 $v$ の高さ $X - T$ の地点に飛びついたと考えてよい

$T \ge X$ の場合が非自明かもしれない。なぜなら途中で「高すぎるから高度を下げるムーブ」があったかもしれないからだ。ところが

飛び移る行為によっても 1 秒に 1 だけ下がる
高度を下げる行為によっても 1 秒に 1 だけ下がる

というわけで、どっちにしても 1 秒に 1 だけ下がるのだ！！！

以上から、単純に次のような dp 配列を用いた Dijkstra 法で OK

dp[v] ← 木 $v$ に到達するのに要する最短時間

dp[v] の情報から木 $v$ に飛びついた瞬間の高さを復元できるので、次の各木へ飛び移るのに必要な時間も正確な所要時間を求められる。

計算量は $O(M \log N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;
bool chmin(long long &a, long long b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1LL<<50;
int main() {
    int N, M;
    long long X;
    cin >> N >> M >> X;
    vector<long long> H(N);
    for (int i = 0; i < N; ++i) cin >> H[i];

    using Edge = pair<int, long long>;
    using Graph = vector<vector<Edge>>;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        long long w;
        cin >> a >> b >> w;
        --a, --b;
        G[a].emplace_back(b, w);
        G[b].emplace_back(a, w);
    }

    // 頂点 v にたどり着いた時点で dis 秒経過していたとき、頂点 v での高さ
    auto calc_height = [&](int v, long long dis) -> long long {
        long long res = max(0LL, X - dis);
        chmin(res, H[v]);
        return res;
    };
    // 頂点 from に高さ height の状態で出発して、頂点 to にたどり着くまでの時間
    auto calc_dist = [&](int from, int to, long long height, long long w) -> long long {
        if (height - w >= H[to]) return height - H[to];
        else if (height - w >= 0) return w;
        else if (H[from] - w >= 0) return w * 2 - height;
        else return INF;
    };
    
    vector<long long> dp(N, INF);
    dp[0] = 0;
    priority_queue<pair<long long, int>,
                   vector<pair<long long, int>>,
                   greater<pair<long long, int>>> que;
    que.push({0, 0});
    while (!que.empty()) {
        auto tmp = que.top();
        que.pop();
        int v = tmp.second;
        long long dis = tmp.first;
        if (dis > dp[v]) continue;

        long long height = calc_height(v, dp[v]);
        for (auto e: G[v]) {
            int nv = e.first;
            long long w = e.second;
            if (chmin(dp[nv], dp[v] + calc_dist(v, nv, height, w))) {
                que.push({dp[nv], nv});
            }
        }
    }
    long long h = calc_height(N-1, dp[N-1]);
    long long res = dp[N-1] + (H[N-1] - h);
    cout << (res < INF ? res : -1) << endl;
}