C++で解くガソリンスタンド周回問題 ― 車が出発すべき給油所の求め方

問題概要

円周上に n 個のガソリンスタンド（給油所）があるとします。各給油所について、次の2種類のデータが与えられます。

• 各給油所が保有している燃料の量
• ある給油所から次の給油所までの距離

このとき、車が円周を一周できる最初の出発地点を求めるのが目的です。ただし、車は「1単位の燃料で1単位の距離」を走行できるものと仮定します。

例として、4つの給油所があり、燃料量と次の給油所までの距離が [(4, 6), (6, 5), (7, 3), (4, 5)] と与えられている場合を考えてみましょう。この場合、車が一周を完走できる最初の出発地点は「2番目の給油所」です。したがって、出力は start = 1（2番目の給油所のインデックス）となります。

解法のアプローチ：キューを使った効率的なアルゴリズム

この問題はキュー（queue）を活用することで効率的に解くことができます。キューには現在検討中の周回路線を格納していきます。

具体的な手順は以下の通りです。

1. 最初の給油所をキューに挿入します。
2. 周回が完了するか、現在の燃料残量が負になるまで、順次給油所をキューへ挿入していきます。
3. 燃料残量が負になった場合は、その出発点では完走できないため、キューが空になるまで先頭の給油所を削除し続けます。

この手法により、全探索を行わずとも O(n) の計算量で答えを求められます。

実装例

それでは、実際のC++コードを見ながら理解を深めましょう。

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

入力

[[4, 6], [6, 5], [7, 3], [4, 5]]

出力

Index of first gas station : 1

コードのポイント

• curr_gas：現在のルートにおける燃料の収支（燃料量 − 移動距離の累積）を表します。
• start_point：候補となる出発地点のインデックスです。燃料が不足した場合は次の候補へ進みます。
• end_point：周回の終端（次に追加する給油所）を指します。
• 一周しても解が見つからない場合は -1 を返し、「No solution」と表示されます。

このように、キューによる両端の管理を組み合わせることで、無駄な再計算を避けながら最適な出発地点を効率よく特定できます。