C++で円周上のすべてのガソリンスタンドを1周できる最初の出発地点を見つける方法

問題の概要

円周上に n 個のガソリンスタンドがあるとします。このとき、次の2種類のデータが与えられます。

• 各ガソリンスタンドが保有しているガソリンの量
• あるガソリンスタンドから次のガソリンスタンドまでの距離

求めたいのは、トラックが出発して円を一周できる最初の出発地点です。なお、1リットルのガソリンで1単位の距離を走行できるものとします。

例として、4つのガソリンスタンドがあり、各スタンドの「ガソリン量と次のスタンドまでの距離」が [(4, 6), (6, 5), (7, 3), (4, 5)] となっている場合を考えます。このとき、トラックが一周を完走できる最初の出発地点は2番目のガソリンスタンドです。したがって、出力は start = 1(2番目のポンプのインデックス)となります。

キューを使った効率的な解法

この問題は、全ての出発地点を順番に試す総当たり方式(O(n²))よりも、キュー(queue)を活用することで O(n) で効率的に解くことができます。

基本的な考え方は以下の通りです。

• キューには現在の巡回経路(候補となる区間)を保存します。
• まず最初のガソリンスタンドをキューに挿入し、巡回が完了するか、現在のガソリン残量が負になるまでスタンドを追加していきます。
• 残量が負になった場合は、キューが空になるまで(または残量が回復するまで)先頭のスタンドから削除し、新たな出発候補へ移ります。

この処理を繰り返すことで、一周を完走できる出発インデックスを一度の走査で特定できます。

サンプルコード(C++)

#include <iostream>
using namespace std;
class pump {
    public:
        int petrol;
        int distance;
};
int findStartIndex(pump pumpQueue[], int n) {
    int start_point = 0;
    int end_point = 1;
    int curr_petrol = pumpQueue[start_point].petrol - pumpQueue[start_point].distance;
    while (end_point != start_point || curr_petrol < 0) {
        while (curr_petrol < 0 && start_point != end_point) {
            curr_petrol -= pumpQueue[start_point].petrol - pumpQueue[start_point].distance;
            start_point = (start_point + 1) % n;
            if (start_point == 0)
                return -1;
        }
        curr_petrol += pumpQueue[end_point].petrol - pumpQueue[end_point].distance;
        end_point = (end_point + 1) % n;
    }
    return start_point;
}
int main() {
    pump PumpArray[] = {{4, 6}, {6, 5}, {7, 3}, {4, 5}};
    int n = sizeof(PumpArray)/sizeof(PumpArray[0]);
    int start = findStartIndex(PumpArray, n);
    if(start == -1)
        cout<<"No solution";
    else
        cout<<"Index of first petrol pump : "<<start;
}

実行結果

Index of first petrol pump : 1

コードのポイント

• start_point / end_point: 巡回候補となる区間の先頭と末尾を表す2つのポインタ(インデックス)です。配列を環状に扱うため、剰余演算 % n で折り返しています。
• curr_petrol: 現在の区間でのガソリン収支(補給量 − 移動距離)の累積値です。これが負になると、その出発地点では一周できないことを意味します。
• 戻り値 -1: どの出発地点でも一周できない場合(全体のガソリン総量が総距離に満たない場合など)は「No solution」として -1 を返します。

このアルゴリズムにより、スタンド数が増えても線形時間 O(n) で最適な出発地点を求めることができます。