環状線の駅間の最短距離を求めるC++コード

2つの整数 s と t、さらに n 個の要素を持つ配列 D が与えられているとします。ドリームランド地下鉄の環状線には n 個の異なる駅があります。隣接する駅同士の距離はすべて分かっており、D[i] は駅 i と駅 i+1 の間の距離、D[n-1] は駅 (n-1) と駅 0 の間の距離を表します。このとき、駅 s から駅 t までの最短距離を求める必要があります。

例えば、入力が s = 1、t = 3、D = [2, 3, 4, 9] の場合、出力は 5 になります。

解法の手順

この問題は、以下の手順に従って解くことができます。

n := D のサイズ
(n + 1) サイズの配列 arr を定義し、0 で初期化する
i := 1 とし、i <= n の間、i を 1 ずつ増やしながら繰り返す：
    arr[i] := D[i - 1]
    sum1 := sum1 + arr[i]
s > t である場合は：
    s と t を入れ替える
i := s とし、i < t の間、i を 1 ずつ増やしながら繰り返す：
    sum2 := sum2 + arr[i]
sum2 と (sum1 - sum2) のうち最小値を返す

ここでのポイントは、環状線では目的の駅へ「一方回り」と「反対回り」の2通りの経路があるということです。片方の経路の距離が sum2 であれば、もう片方の経路の距離は (sum1 - sum2) となります。したがって、この2つの値のうち小さい方が最短距離になります。

C++実装例

理解を深めるために、実際のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(int s, int t, vector<int> D){
    int n = D.size(), sum1 = 0, sum2 = 0;
    vector<int> arr(n + 1, 0);
    for (int i = 1; i <= n; i++){
        arr[i] = D[i - 1];
        sum1 += arr[i];
    }
    if (s > t)
        swap(s, t);
    for (int i = s; i < t; i++)
        sum2 += arr[i];
    return min(sum2, sum1 - sum2);
}
int main(){
    int s = 1;
    int t = 3;
    vector<int> D = { 2, 3, 4, 9 };
    cout << solve(s, t, D) << endl;
}

入力

1, 3, { 2, 3, 4, 9 }

出力

5

このアルゴリズムの計算量は O(n) であり、環状線上の任意の2駅間の最短距離を効率的に求めることができます。まず一周の総距離を求めておき、片方向の距離との差から逆方向の距離を導き出すというシンプルな考え方が応用の幅広いテクニックです。