SoundHound Inc. Programming Contest 2018 -Masters Tournament-_D_Saving Snuuk

青色の問題.最小コストは求められる.そっからどうするか.グラフの問題は難しい.

問題の説明

ある国には円とスヌークという2つの通貨が存在する. $n$ 個の都市は $m$ 本の電車で繋がっており,どの都市からどの都市へも行ける事が保証されている.

$m$ 本の電車には運賃が設定されており, $i$ 番目の電車の運賃を円で払う場合は $a_i$ 円,スヌークで払う場合は $b_i$ スヌークを払う必要がある.( $1 \le i \le m$ ).

移動に際し, $n$ 個の都市のどこか $1$ カ所で円をスヌークに両替したいと考えています(移動始めと終わりの都市で両替してもよい).両替をする際は持っている $X$ 円をすべて $X$ スヌークに変えなければなりません. 最初,両替所はすべての都市で使用可能であるが, $i$ 番目の両替所は $i$ 年後に閉鎖され, $i$ 年後から使用出来なくなります.

始めに $10^{15}$ 円を持ち,できるだけ多くのスヌークを残した状態で都市 $s$ から $t$ へ向かいます. $0~n-1$ 年のそれぞれについて移動した際のスヌークの最大量を出力しなさい.ただし,移動中に年を跨ぐ事はないとします.

制約

$2 \le n \le 10^{5}$
$1 \le m \le 10^{5}$
$1 \le s, t \le n$
$1 \le a_{i}, b_{i} \le 10^{9}$

考えた事

問題が込み入っていて難しい.とりあえず年数を経る毎に徐々に選択肢が狭まって行く事はわかるだろう. となれば考えたくなるのは選択肢が狭い方であろう.最終年( $n-1$ 年)から考えてみよう.

$n-1$ 年目の時,都市 $1~n-1$ の両替所は閉鎖されており,使えるのは都市 $n$ の両替所のみである.つまり,実質的に $n$ を経由し,両替する事が必須の条件となる.

という事は, $n-1$ 年目では( $s→n$ まで円を用いて移動する時の最小コスト)+( $n→t$ までスヌークを用いて移動する時の最小コスト)とすればよい.

$s→n$ の移動の最小コストを求める問題は「単一始点最短路問題」として知られており,ここではDijkstra法を用いて解く.¹ Dijkstra法の実装は最後に貼るコードを参照のこと.計算量は $O(m \log n)$ であり,現実的である.

$n→t$ 間も同様に行えばいいだろうか.そうとはいかない. 次に $n-2$ 年目を考えてみよう.問題文から両替所として使えるのは $n-1$ , $n$ のいずれかに絞られる. $n$ に関してはさきほど考えたので考えなくてよい.

$s→n-1$ に関しては $s→n$ において用いたDijkstraを利用すればよい.しかし, $n-1→t$ を移動する際の最小コストの計算はどうしようか.

もちろん $n-1$ を始点としたDijkstra法で求められる.しかし,それを年数が減る度に一々求め直していたらムダが多いのは明らかである.実際計算量も $O((m \log n) * n)=O(mn \log n)$ となりTLEする.

これを解決するためにはどうしようか.なるべくDijkstra法を使う回数を減らしたい.ここでのポイントは終点が $t$ で固定されている点だ.そして,都市 $n$ 個を繋ぐ鉄道には向きがない,つまりこれは無向グラフである点もポイントである.

つまり,ここでの答えは $n→t$ , $n-1→t$ と見るのではなく, $n←t$ , $n-1←t$ と見る事だ.そうする事で $t$ 始点でのDijkstra法を使い回す事が出来,計算量も間に合う.²

まとめよう.この問題はまず $s$ を始点,コストを円として,Dijkstra法を行い,次に $t$ を始点,コストをスヌークとしてDijkstra法を行えばよい.以降,両替所が $i$ であるときの最小コストを便宜的に前者を $ds _{i}$ ,後者を $dt _{i}$ と表記する.

最後に各年の移動コストの最小値を出して終わりにしよう.ここでも下( $n-1$ 年)から見る考え方が活きる.

まず $n-1$ 年の時の最小コストはもちろん $ds _{n}+dt _{n}$ である.両替所は $n$ しか使えないからだ.

次に $n-2$ 年を考える.両替所の候補は $n-1, n$ の二カ所のみなので,最小コストは $min(ds _{n-1}+dt _{n-1}, ds _{n}+dt _{n})$ である.

ここで $ds _{n}+dt _{n}$ が再度参照されている事に気付くだろう.勘の良い方はもうピンときたはずだ.

ある $i$ 年での移動にかかる最小コストは, $min((ds _{i+1}+dt _{i+1}), (i+1年までの最小コスト))$ となる.これは簡単なDPで実装ができる.

repd(i, n - 1) { CHMIN(dif.at(i), dif.at(i + 1)); }

として後ろから決めていけばいい.以上で $n-1$ 年から $0$ 年まで決めて行く事でこの問題は解ける.

この問題で難しかった点は計算量である.雑多な方針が(Dijkstra法を知っていれば)すぐに思いつく.しかしそれを考え無しに実装するだけではTLEとなる.始点と終点を入れ替える,逆の年数から決めていくといった工夫が必要だ. 大事なのは選択肢が多いものを後回しにして,選択肢が少ない方から決定し,それを活用出来ないかを考える事である.これはDPを始めとして競技プログラミングで頻出のテクニックであり,さまざまな場面でみかけるものだ.青色レベルの高度な問題でもこういった基盤の部分をきっちり付いてくる点は恐ろしく,その点において非常に教育的な問題であった.この問題を解いた経験を忘れずに,今後の競技プログラミングの進捗を増やしていきたい.

本日もお読みくださりありがとうございました.

プログラム

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<long long>;
const long long INF = 1e18;
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
template <class T>
inline T CHMIN(T& a, const T b) {
    return a = (a > b) ? b : a;
}
struct edge {
    ll to;
    ll cost;
};
vll dijkstra(ll start, ll choten,
             vector<vector<edge>>& G) {  // 開始地点と頂点数, グラフ
    priority_queue<pll, vpll, greater<pll>>
        que;                // firstが最短距離,secondが頂点
    vll dist(choten, INF);  // startからの最短距離の配列,最初はINF
    dist.at(start) = 0;     // startだけで0で置いとく
    que.push(pll(0, start));
    while (!que.empty()) {
        pll p = que.top();
        que.pop();
        ll v = p.second;
        if (dist.at(v) < p.first) {
            continue;
        }
        rep(i, G.at(v).size()) {
            edge e = G.at(v).at(i);
            if (dist.at(e.to) > dist.at(v) + e.cost) {
                dist.at(e.to) = dist.at(v) + e.cost;
                que.push(pll(dist.at(e.to), e.to));
            }
        }
    }
    return dist;
}
int main() {
    ll n, m, s, t;
    cin >> n >> m >> s >> t;
    s--;
    t--;
    vll ui(m), vi(m), ai(m), bi(m);
    vector<vector<edge>> G(100010);// グラフの情報を格納
    rep(i, m) {
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        u--;
        v--;
        edge p = {v, a};// s→iの最小コストを先に決める
        edge q = {u, a};
        G.at(u).push_back(p);
        G.at(v).push_back(q);
        ui.at(i) = u;
        vi.at(i) = v;
        ai.at(i) = a;
        bi.at(i) = b;
    }
    vll dista = dijkstra(s, n, G);
    rep(i, 100010) { G.at(i).clear(); }
    rep(i, m) {
        edge p = {vi.at(i), bi.at(i)};// i←tの最小コスト
        edge q = {ui.at(i), bi.at(i)};
        G.at(ui.at(i)).push_back(p);
        G.at(vi.at(i)).push_back(q);
    }
    vll distb = dijkstra(t, n, G);
    vll dif;
    rep(i, n) { dif.push_back(dista.at(i) + distb.at(i)); }// s→i→tの最小コストを格納    
    repd(i, n - 1) { CHMIN(dif.at(i), dif.at(i + 1)); }
    // 後ろと比較
    rep(i, n) {
        ll ans = 1e15 - dif.at(i);
        cout << ans << endl;
    }
}

Bellman-Ford法を選ばない理由としては,この方法であると計算量が $O(nm)$ となり,間に合わないからである.↩
この考えは有向グラフでも活用できる.グラフの辺の向きをすべて逆転させて,終点を始点とみなしてDijkstra法を行えば始点,終点,中間点をすべて通る場合のコストの最小値を求められる.↩

garakutagoya

興味、関心のあったこと、そして私の気持ちなどを残していきたい

SoundHound Inc. Programming Contest 2018 -Masters Tournament-_D_Saving Snuuk

問題の説明

制約

考えた事

プログラム