E - Skiing と ポテンシャル

問題

atcoder.jp

解法の前のお勉強

辺のコストの持ち方以外は難しくない。制約的に、Dijkstra法を用いることで解ける。さて、問題はコストが負になりうるという点である。
Dijkstraのアルゴリズムは、負の辺があると動作しない。ならば、負の辺を消してしまえば良い。

具体的には、ポテンシャルという概念を導入する。
ここでは、ながたかなさんの記事とできるだけ同じ記法を使って説明してみる。下の参考文献にもリンクがあります。

（感覚的には、最短経路の性質が壊れないように、適当な値を加えて辺を変える。多分)

頂点 を結ぶ辺を とする。各頂点ごとにポテンシャルを考え、ポテンシャル導入した辺をを次のように定義する。ただし、変更後の辺はコストが正になってほしいので、ポテンシャルは次のようにしておく。

この辺を用いたときの最短経路の求め方をエミュレートしてみる。は、上で定義した辺()を用いたときの、始点からまでの最短距離を表す。

ここで、 と考えると

となって、置き換えると最短距離のまんまになる。辺のコストを書き換えただけなのに、元の辺のコストが現れた…だと

これだけだと? となるので、口語的な説明を追記してみる。

まずはじめに、との差は、のポテンシャルの差になる。頂点のポテンシャルの差分(始点と終点）のみに依存するため、変更後の辺()上で求めた最短路も、変更前の辺()上で求めた最短路になる。

始点と終点以外のポテンシャルの値は辺を移動するときに消えそうだな、という感じもするが、せっかくなのできちんと説明しておく。

さて、最終的にほしいのはではなく、ポテンシャルを導入する前の最短経路である。今までは始点を省略していたが、ここからは と のように記述することにする。

結論から言うと、 が成り立つ（らしい）。

正直全然わからないので、もう少し詳しく見てみる。

という最短路だったとしよう。とする。

一方で、

これを比較するとさっきの式がでる。
なるほど、たしかに端点だけを考慮するだけで良い。すごい。

解法

はい。それではようやく問題を解き始め
最大化なので、最小化に言い換えてDijkstra法を適用することにする。これに伴って、のときは, のときは と言い換えることができる。

さて、ここからポテンシャルを導入することを考える。

として、ポテンシャルを導入してみる。

のとき

のとき

良さそう。この辺を使って解くと問題が解が得られる。

解法

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

using Int = long long;
constexpr Int inf = (1LL  << 60);

inline Int potential(Int a, Int b,vector<Int>&H){
    
    if(H[a] > H[b])
    {
        return H[a] - H[b];
        
    } else
    {
        return 0LL;
    }
}

int main(){
    
    int N,M;
    cin >> N >> M;
    
    vector<Int>H(N);
    vector<vector<pair<int,Int>>>edge(N);
    
    for(auto& h : H){
        cin >> h;
    }
    
    for(int i = 0; i < M; ++i){
        int u,v; cin >> u >> v;
        --u; --v;
        edge[u].emplace_back(v,potential(v,u,H));
        edge[v].emplace_back(u,potential(u,v,H));
    }
    
    vector<Int>d(N,inf);
    d[0] = 0;
    
    priority_queue<pair<Int,int>,vector<pair<Int,int>>,greater<>> que;
    que.emplace(d[0],0);
    
    while(not que.empty()){
        auto [td,cv] = que.top();
        que.pop();
        
        if(d[cv]  <  td)
            continue;
        for(auto p : edge[cv]){
            int nv = p.first;
            Int cst = p.second;
            if(d[nv] <= cst + d[cv])
                continue;
            d[nv] = cst + d[cv];
            que.emplace( d[nv], nv);
        }
    }
    Int ans = 0;
    for(int i = 0; i < N; ++i)
        ans = max(ans, -1 * (d[i] - H[0] + H[i]));
    
    cout << ans << endl;
}

参考

すこし難しいがとても詳しい。
https://qiita.com/ngtkana/items/d7fc4463e56b966d1ebf

理解にとても役立った
niuez.hatenablog.com

やはり先人は偉大で、こういった記事で理解が何倍も早く進む。感謝します。

謝辞

この記事を書く（勉強する）に至って、Twitter上で質問に答えてくださった皆様に感謝します。
ありがとうございました。