貪欲法
01 / 共通の仕組み
各ステップで局所最適を確定し、その確定が後で覆らないことを示す。 バックトラックも DP テーブルも要らない:交換論法でどの貪欲な選択を入れ替えても 改善できないと示すか、先行論法で貪欲がどの接頭辞でも遅れないと示す。 この発想を 3 つの古典的サブパターンに落とし込む: 区間でソートして取る、配列上で到達範囲を追う、累積量で「失敗したらリセット」。
01 / 一文での本質
タンクは一周のどこでも負になってはいけない。実行タンクがある接頭辞で 0 を下回ったら、その接頭辞のすべての始点が死んでいる — 開始点を失敗の先までリセットする。
問題一周できる開始点を見つけるgas[1, 2, 3, 4, 5]cost[3, 4, 5, 1, 2]
長さ 5 の並列配列が 2 つ。各駅で diff = gas − cost がタンクに入る。タンクはどこでも負になってはいけない。
ステップ
0 / 9
i
—
tank
0
start
0
0 / 9
02 / パターンの骨格
# 1 パス、2 つの累積total ← 0; tank ← 0; start ← 0for i in 0..n−1:diff ← gas[i] − cost[i]total += difftank += diffif tank < 0:start ← i + 1 # この区間は丸ごと死亡tank ← 0return start if total >= 0 else −1
03 / このパターンを使うべき合図
「環状経路、一周回る」
LC 134 の典型的な言い回し。環状のステーション、
gas[i] で給油し cost[i] で消費するタンク、一周回って戻れる開始位置を探す。環を線形化する — total ≥ 0 ならば妥当な開始点が必ず存在し、 リセットループがそれを見つける。「累積和が常に非負」
「この累積量が一度でもゼロを下回るか?」と問われるたびに — 残高、燃料、エネルギー、水位 — 同じ 1 パス・リセットの技が使える。 失敗する接頭辞は妥当な開始接頭辞にはなり得ない。
「最大部分和(Kadane)」
LC 53 は符号を反転した同形:累積和がゼロを下回ったらゼロにリセットする — 累積和を負に引きずる接頭辞は後続要素にとって重荷でしかないから。 ガスステーションは start をリセット、Kadane は sum をリセット。 証明は同じ。
「最長妥当接頭辞 / 巻き戻し」
入力が環状で答えが連続する弧、かつ 1 回の走査で大半の候補を除外できる証明があるとき。 リセット技と最後の全体可能性チェックを組み合わせる。
04 / よくある落とし穴
i.
最後に
total を確認し忘れる。最後の
total >= 0 チェックを忘れると、 実際にはループが不可能な入力でも start を返してしまう — リセットは常に start を前進させるので、退化した入力でもどこかを指す。 合計は「そもそも妥当な開始点が存在するか」を、 リセットループは「具体的にどれか」を答えるだけ。ii.
リセットの 1 ずれ。
i を処理した後に tank < 0 なら、新しい開始は i + 1、i ではない。i 自身も死んでいる: 接頭辞 [start..i] がすでに負に沈んでいるので、その中のどの駅も妥当な始点になり得ない。 1 ずれると死んだ駅を再選し、運次第では正答を返すこともあるが、 意地悪な入力では返さない。iii.
証明を取り違える — 各開始点を O(n²) で試す。
つい「各開始点で一周シミュレートする」に戻ってしまう。鍵となる洞察は失敗した接頭辞はその中の全開始点を殺すこと:
start..i が負に沈むなら、任意の j ∈ [start, i] について j..i も負である (前方の正のバッファを取り去っただけのもの)。これがパターンのすべて — 1 回の走査で十分。05 / LeetCode で練習
難易度順に 4 問。LC 53 は「符号付き 1 配列上の同じリセット技」 — Kadane に慣れていなければ先に解くと良い。
— / どれをいつ使うか
区間スケジューリング
入力が区間のリストで「最大いくつまで重ならないように選べるか」を問う時に使う。終点でソートし、直近に採用した終点を始点が超えている区間を順に取る。 交換論法が「最早終了」が常に安全だと保証する。
終点でソート · LC 435 · LC 452
ジャンプゲーム
各要素がそこから動ける距離を決めるときに使う。左から右へ走査し、今までに到達可能な最遠の添字を保持する。 走査位置がその境界を越えたら、終点に到達できない。
最遠を追う · LC 55 · LC 45
ガスステーション
(環状または線形の)経路で、ある累積量が常に非負でなければならないときに使う。 実行中の合計がゼロを下回った瞬間に開始位置を次へリセット — 失敗する区間は妥当な開始接頭辞にはなり得ない。
失敗で即リセット · LC 134 · LC 53