貪欲で輪を 1 周できる出発点を求める

輪になった配送の道で、電気自動車が 1 周できる出発の充電所の番号を返す。電池が足りなくなったら、その次の充電所から出発し直すと決めるだけで、前から 1 回なめて答えが出ます。

海外で定番の問題リスト 4 本には入っていません

問題

輪になった配送の道に、充電所が番号 0 から順に並んでいます。充電所 i では電気を charge[i] だけ足せ、充電所 i から次の充電所 (最後の充電所の次は 0 番) へ進むには電気を cost[i] だけ使います。電池が空の電気自動車で、どこか 1 つの充電所から出発し、番号の増える向きに 1 周して出発した充電所へ戻りたいとします。1 周できる出発の充電所の番号を返し、どこから出ても 1 周できなければ -1 を返す関数を書いてください。

1 周できる出発の充電所があるなら、それは 1 つだけになるような入力だけが渡されます
進む途中で電気がちょうど 0 になるのはかまいませんが、負になる所へは進めません
電池には上限がなく、足した電気は全部たまります
charge と cost の長さは同じで 1 以上 100000 以下、値はどれも 0 以上 10000 以下です

入力と出力の例

例 1

充電所 2 から出ると、電気は 5 - 1 で 4、2 - 3 を足して 3、3 - 2 を足して 4、1 - 4 を足して 1 と、負にならずに戻れます。ほかの充電所からでは途中で足りなくなります。

charge = [3, 1, 5, 2] cost = [2, 4, 1, 3]

例 2

足せる電気の合計は 6、使う電気の合計は 7 なので、どこから出ても 1 周できません。

charge = [2, 2, 2] cost = [3, 2, 2]

-1

例 3

充電所が 1 つだけで、足した 4 をちょうど使い切って戻れます。

charge = [4] cost = [4]

面接での聞かれ方

面接では、ガソリンスタンドの話として出されることが多いです。

「輪になった道にスタンドがあります。1 周できる出発点を答えてください」
最初に全部の出発点を試す書き方を話し、「O(n) にできますか」と聞かれる流れがよくあります
書き終えたあとに「なぜ足りなくなった所の次から出直してよいのですか」と、理由を聞かれることもあります

答えが複数あるときにどれを返すかを、書く前に確かめておきます。この問題では、答えは多くとも 1 つと決めています。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

素直に考えると、出発の充電所を 1 つずつ決めて実際に 1 周させ、途中で電気が負にならないかを調べることになります。出発点が n 通り、1 周に n 歩なので O(n²) かかります。

段 2

まず、足せる電気の合計が使う電気の合計より少なければ、どこから出ても 1 周できません。逆に、合計が足りていれば、1 周できる出発点が必ずあることが知られています。残る問題は、どこから出るかです。

段 3

充電所 s から出て、充電所 i で次へ進む電気が足りなくなったとします。s と i の間のどの充電所から出ても、そこへは電気が 0 以上たまった状態で着いていたので、そこから出直しても i でやはり足りなくなります。だから、次の出発の候補は i + 1 に飛ばせます。前から 1 回なめて、電気が負になるたびに候補を次の充電所へ移し、電気を 0 に戻します。最後に合計が足りていれば、残った候補が答えです。

解答

Python

def start_station(charge, cost):
    total = 0
    tank = 0
    start = 0
    for i in range(len(charge)):
        gain = charge[i] - cost[i]
        total += gain
        tank += gain
        if tank < 0:
            start = i + 1
            tank = 0
    if total < 0:
        return -1
    return start

JavaScript

function startStation(
  charge, cost
) {
  let total = 0;
  let tank = 0;
  let start = 0;
  const n = charge.length;
  for (let i = 0; i < n; i++) {
    const gain = charge[i] - cost[i];
    total += gain;
    tank += gain;
    if (tank < 0) {
      start = i + 1;
      tank = 0;
    }
  }
  return total < 0 ? -1 : start;
}

Go

func startStation(
	charge, cost []int,
) int {
	total, tank, start := 0, 0, 0
	for i := range charge {
		gain := charge[i] - cost[i]
		total += gain
		tank += gain
		if tank < 0 {
			start = i + 1
			tank = 0
		}
	}
	if total < 0 {
		return -1
	}
	return start
}

合計が足りているときは、最後の充電所で電気が負になることはありません。そこで負になるなら、それまでの区切りの合計もどれも負なので、全体の合計も負になるからです。だから start が n になって範囲の外を返すことはありません。

計算量

時間は O(n) です。充電所を前から 1 回なめ、1 か所ごとの手間は一定です
使う記憶は O(1) です。持つのは合計、いまの電気、候補の番号の 3 つだけです
段 1 の全部の出発点を試す書き方は O(n²) かかります

よくある間違い

合計を確かめずに候補を返す。例 2 では、前から見ると充電所 0 で -1 になって候補が 1 へ移り、そのあとは 0 のまま負にならないので、合計を見ないと 1 を返します。1 周できないことは合計でしか分かりません
候補を i にする。 足りなくなった充電所 i から出ても、i から次へ進む所で同じく足りなくなります。候補は i + 1 です
電気が 0 になったら出直す。条件を tank <= 0 と書くと、例 3 の充電所 1 つで電気がちょうど 0 になり、候補が 1 に移って範囲の外を返します。出直すのは負になったときだけです
輪を 2 周なめて確かめ直す。合計が足りていれば候補で必ず 1 周できるので、2 周目は要りません。書いても答えは合いますが、理由を説明できないと、面接ではかえって迷っているように見えます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def start_station(charge: list[int], cost: list[int]) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(start_station([3, 1, 5, 2], [2, 4, 1, 3]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します