OUPC β「Increasing Path」解説

Pocket

こんにちは、ふるやん（@furuya1223）です。

本日 Hackerrank にて開催された OUPC β に参加いただいた方は、ありがとうございます。

参加いただいていない方は、ぜひ問題を見てみてください。

コンテストページ：https://www.hackerrank.com/contests/oupc-beta/challenges

私はこのコンテストで、 Increasing Path の writer と、他の問題の tester、Python 解作成などを担当しました。

みんな教育的な良い問題を作るなあと思います。私の問題はどうでしょうか。

私はプログラミングコンテストの問題を作るのが初めてなので、Slack で色々な案を出して議論してを繰り返しました。作問って楽しいね。

同時に作問の難しさ・大変さも学びました。

次に活かすぞ！

それでは、問題の解説をどうぞ。

問題概要

問題 URL: https://www.hackerrank.com/contests/oupc-beta/challenges/increasing-path

$N$ 頂点 $M$ 辺の長さ付き無向グラフが与えられます。

頂点 $1$ から頂点 $N$ まで、使用する辺の長さが真に大きくなっていくように移動するときの、合計経路長の最小値を出力してください。

そのような移動が不可能なら $-1$ を出力してください。

以下、使用する辺の長さが真に大きくなっていくという条件を単に “条件” と書きます。

サンプル

7 8

1 2 5

1 4 8

2 3 6

3 5 7

4 5 9

5 6 10

5 7 8

6 7 11

辺の長さについての条件が無い場合、頂点 $1$ から頂点 $4,5$ を経由して頂点 $7$ へ移動して合計距離 $8+9+8=25$ が最短です。

しかし、この移動経路では使用する辺の長さが $9\rightarrow 8$ と減少している箇所があるため、条件を満たしません。

もし、頂点 $1\rightarrow 4\rightarrow 5$ と移動した場合、辺の長さが減少しないためには次に頂点 $6$ に移動する必要があります。この場合、合計距離は $8+9+10+11=38$ となってしまいます。

そのため、あえて頂点 $1\rightarrow 2\rightarrow 3\rightarrow 5$ と少し遠回りをして、辺 $(5,7)$ を通れるようにしておくのが最善です。このとき、合計距離は $5+6+7+8=26$ となります。

解説

始点が固定されているので、単一始点最短経路問題として考えます。

つまり、頂点 $1$ から全頂点への最短経路長を計算します。

長さが $k$ である辺が、頂点 $1$ からどこかへの最短経路に使用されたとします。

このとき、その辺の端点のうち始点側（頂点 $1$ からの距離が小さい側）の頂点について、「そこまでは長さ $k-1$ 以下の辺で条件を満たして移動することができる」ということが言えます。

また、長さ $k$ の辺を使って移動したあとは、長さ $k$ 以下の辺を使って移動してはいけません。

このように考えると、長さが短い辺から順番に処理していくと良さそうです。

また、使用する辺の順番の前後関係が明らかになっているので、DP 的に考えることができそうです。

ということで、DP 的に考えてみます。

「長さ $k$ 以下の辺だけを使って条件を満たして移動する場合の、頂点 $1$ から各頂点への最短経路長（不可能なら $\infty$）」が全頂点について分かっているとします。

頂点 $v$ におけるこの値を $dist[k][v]$ とします。$dist[k][1]=0$ です。

このとき、$dist[k+1][v]$ の値は、以下のように計算することができます。

$dist[k+1][v]=\min(dist[k][v], \min_{d(u,v)=k+1}(dist[k][u]+k+1))$

ここで、$d(u,v)$ は辺 $(u\rightarrow v)$ の長さです（辺が無い場合は未定義もしくは $\infty$）。

つまり、長さ $k+1$ の辺を使って最短距離の更新（緩和）を行います。

この $dist[k][v]$ を順に更新していくことで、最終的な答え $dist[\max(c)][N]$ を得ることができます。$\max(c)$ は辺の長さの最大値です。

サンプルにおける $dist[k][v]$ の表は下記のようになります。

赤字の部分において距離の更新が行われています。

$\infty$ は薄いグレーにしています。

この表において、頂点 $5$ の距離は $18$ になってから $17$ に減少していますが、頂点 $7$ への辺 $(5,7)$ を用いた更新は、距離が $17$ に更新される前に行われているため、適切な値になっています。

最後の更新において、辺 $(6,7)$ を用いて頂点 $7$ への距離 $27+11=38$ が計算されますが、 $26$ より長いので更新されません。

この表を計算すれば問題を解くことができます。

ただし、このままでは $dist[k][v]$ の表のサイズが $M\times N$ などになってしまい、メモリが足りません。

そこで、1 つ目の添字を持たず、配列の使い回しをします。

つまり、長さの短い辺 $e$ から順に

$dist[e.to]\leftarrow \min(dist[v], dist[e.from]+e.length)$

として更新していきます。ここで、 $e.from, e.to, e.length$ はそれぞれ辺 $e$ の始点・終点・長さです。

こうすることで、配列のサイズが $N$ になり、更新回数が $M$ となって、間に合いそうになります。

ただし、配列の使い回しをする場合、同じ長さの辺の存在に注意する必要があります。

辺を長さの昇順にソートして更新を行う過程で、長さ $k$ の辺で更新したあとに長さ $k$ の別の辺で更新すると、同じ長さの辺を連続して使用する経路が採用される可能性があります。

例えば上の図で、辺を長さでソートしたときに $(1,2)$ が先に現れた場合、そのまま更新すると

更新前：$dist[v]={0,\infty,\infty}$

辺 $(1,2)$ で更新後：$dist[v]={0,5,\infty}$

辺 $(2,3)$ で更新後：$dist[v]={0,5,10}$

となり、不正解である $10$ を出力してしまいます。（正解は $-1$）

そのため、辺を長さでグループ分けし、同じ長さの辺はまとめて更新するなどの工夫が必要になります。

私の解法（writer 解法）では、長さを key、両端点を value として辺を map<int, pair<int,int>> に格納し、同じ長さの辺たちで更新した距離を全て計算し終えてから実際に $dist$ の値を更新するようにしています。

ちなみに、（頂点, 直前に使った辺の長さ）を頂点とする拡張グラフでダイクストラ法を用いる解法は、グラフを陽に持つとメモリが足りません。

しかし、グラフを陽に持たず工夫するとメモリも時間も間に合うようです。

writer 解（C++）

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

#define repr(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) repr(i, 0, n)
using ll = long long;

constexpr long long INF = (long long)4e18;

int main(void) {
    int N, M;
    cin >> N >> M;
    map<int, vector<pair<int, int>>> edges;
    rep(i, M) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        edges[c].push_back(make_pair(a, b));
        edges[c].push_back(make_pair(b, a));
    }
    vector<ll> dist(N, INF);
    dist[0] = 0;
    // 長さの短い順にチェック
    for (const auto &cost_edge : edges) {
        int cost = cost_edge.first;
        map<int, ll> new_dist; // 保留する距離更新を入れておくメモ
        for (const auto &edge : cost_edge.second) {
            int from, to;
            tie(from, to) = edge;

            // from に到達していなければ無視する
            if (dist[from] == INF) continue;

            // 距離更新を保留しておく
            if (new_dist.find(to) == new_dist.end()) {
                new_dist[to] = dist[from] + cost;
            } else {
                new_dist[to] = min(new_dist[to], dist[from] + cost);
            }
        }
        // 保留した距離更新の実行
        for (const auto &node_dist : new_dist) {
            dist[node_dist.first] =
                min(dist[node_dist.first], node_dist.second);
        }
    }
    if (dist[N - 1] == INF) {
        cout << -1 << endl;
    } else {
        cout << dist[N - 1] << endl;
    }

    return 0;
}

#include <algorithm>

#include <iostream>

#include <map>

#include <vector>

using namespace std;

#define repr(i, a, b) for (int i = a; i < b; i++)

#define rep(i, n) repr(i, 0, n)

using ll = long long;

constexpr long long INF = (long long)4e18;

int main(void) {

int N, M;

cin >> N >> M;

map<int, vector<pair<int, int>>> edges;

rep(i, M) {

int a, b, c;

cin >> a >> b >> c;

a--, b--;

edges[c].push_back(make_pair(a, b));

edges[c].push_back(make_pair(b, a));

}

vector<ll> dist(N, INF);

dist[0] = 0;

// 長さの短い順にチェック

for (const auto &cost_edge : edges) {

int cost = cost_edge.first;

map<int, ll> new_dist; // 保留する距離更新を入れておくメモ

for (const auto &edge : cost_edge.second) {

int from, to;

tie(from, to) = edge;

// from に到達していなければ無視する

if (dist[from] == INF) continue;

// 距離更新を保留しておく

if (new_dist.find(to) == new_dist.end()) {

new_dist[to] = dist[from] + cost;

} else {

new_dist[to] = min(new_dist[to], dist[from] + cost);

}

// 保留した距離更新の実行

for (const auto &node_dist : new_dist) {

dist[node_dist.first] =

min(dist[node_dist.first], node_dist.second);

}

if (dist[N - 1] == INF) {

cout << -1 << endl;

} else {

cout << dist[N - 1] << endl;

}

return 0;

}

writer 解（Python）

#!/usr/bin/env python

from collections import OrderedDict


def main():
    INF = 10**18
    N, M = map(int, input().split())
    edges = OrderedDict()
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if c not in edges:
            edges[c] = []
        edges[c].append((a, b))
        edges[c].append((b, a))

    edges = OrderedDict(sorted(edges.items(), key=lambda x: x[0]))
    dist = [INF] * N
    dist[0] = 0
    for cost, edge_list in edges.items():
        new_dist = OrderedDict()
        for f, t in edge_list:
            if dist[f] == INF:
                continue
            if t not in new_dist:
                new_dist[t] = dist[f] + cost
            else:
                new_dist[t] = min(new_dist[t], dist[f] + cost)
        for n, d in new_dist.items():
            dist[n] = min(dist[n], d)
    if dist[N - 1] == INF:
        print(-1)
    else:
        print(dist[N - 1])


if __name__ == '__main__':
    main()