円形ガスステーション問題とは？
円形に配置されたN個のガスステーションがあります。ステーションiではgain[i]だけ燃料を補給してくれますが、次のステーションまで移動するのにcost[i]だけ消費します。タンクは最初空で、容量制限はありません。
目標は、あるステーションから出発し、時計回りに全てのステーションを一度ずつ巡って元の位置に戻れる出発点を見つけることです。存在しなければ-1を返します。
AlgoNoteではこの問題を親しみやすい「真夜中の夜食トラック」として脚色しました。円形循環道路の屋台を一周するトラックの出発点を探す物語です。
鍵は差(diff)
各地点のdiff[i] = gain[i] - cost[i]を考えると問題が単純になります。
- •
diff[i] > 0→ その地点を通ると燃料が増える - •
diff[i] < 0→ 燃料が減る
全体の合計が負なら、どの出発点でも一周できません。 総消費が総補給を上回るからです。だからまず合計を確認します。
なぜ出発点を次に移すのか？
核心となる貪欲な性質はこうです。
出発候補startから累積和を足していき、地点iで初めて負になったなら、startとiの間のどの地点から出発してもiを越えられない。
証明は簡単です。startからiまでの累積が負なら、中間地点jから出発したj〜i区間の合計は (start〜i合計) − (start〜j-1合計) です。start〜j-1区間はiで初めて負になったので0以上でした。したがってj〜i合計 ≤ start〜i合計 < 0 です。つまりjから出発しても同じくiで詰まります。
だから出発候補をi+1に一気にジャンプさせ、累積タンクを0にリセットしても安全です。このジャンプのおかげで一度のスキャン、つまりO(n)で答えを見つけられます。
動作原理
ステップ1. total = 0, tank = 0, start = 0に初期化します。
ステップ2. 各地点iでdiff = gain[i] - cost[i]をtotalとtankに加算します。
ステップ3. tank < 0ならstart = i + 1に移し、tank = 0にリセットします。
ステップ4. スキャン後、total >= 0ならstartを、そうでなければ-1を返します。
ここで「累積更新」と「出発点移動」は別々の動作です。AlgoNoteの可視化もこの2つをそれぞれ別ステップで示します。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(n) |
| 空間 | O(1) |
全ての出発点で一周を試す単純な解法はO(n²)ですが、上記の貪欲な性質のおかげで一度のスキャン、O(n)で解決します。
例で追ってみる
gain = [2, 4, 1, 6, 3]、cost = [4, 1, 5, 2, 2]ならdiff = [-2, +3, -4, +4, +1]、合計+2です。
- •start=0: diff[0]=-2 → tank=-2 < 0 → start=1へ移動
- •start=1: diff[1]=+3 → tank=3, diff[2]=-4 → tank=-1 < 0 → start=3へ移動
- •start=3: diff[3]=+4 → tank=4, diff[4]=+1 → tank=5
最後まで生き残ったstart=3が答えです。
よくあるミス
- •合計チェック漏れ:
total >= 0を確認せずにstartだけ返すと不可能なケースを見逃します。 - •リセットのタイミング: tankが負になった直後にstartを移し、tankを0にリセットします。
- •円形処理の誤解: この貪欲法はモジュラインデックスなしで一度の線形スキャンで十分です（答えが存在すれば一意）。
AlgoNoteで直接確認しましょう
差がどのように累積され、タンクが0を下回るとき出発点がどうジャンプするか、AlgoNoteでステップごとに確認できます。