Koko Eating Bananas
Kokoはn個のバナナの山を持っており、山iにはpiles[i]本のバナナがあり、使える時間はh時間です。彼女は1時間あたりに食べるバナナの本数kを整数で決め、その速度を保ちます。1時間ごとに、1つの山からk本のバナナを食べます。その山に残っているバナナがk本未満の場合は、その山を食べきって、1時間が終わるまで休みます。h時間以内にすべての山を食べきれる、最小のkを返してください。
関数
- pilesinteger-array
- 各山にあるバナナの数
- hinteger
- Kokoが持っている時間数
- 戻り値integer
- h時間以内にすべての山を食べ終える、バナナ毎時で表した最小の整数の食べる速さ
制約
1 ≤ piles.length ≤ 50001 ≤ piles[i] ≤ 109piles.length ≤ h ≤ 109なので、答えは必ず存在します。
例
- 入力
- piles = [4, 10, 7, 3]h = 6
- 出力
- 5
- 説明
- 速度5では、山4、10、7、3にかかる時間はそれぞれ1、2、2、1時間で、合計6時間となり、条件に収まります。速度4では、それぞれ1、3、2、1時間かかり、合計7時間です。
- 入力
- piles = [30, 11, 23, 4, 20]h = 5
- 出力
- 30
- 説明
- 5つの山と5時間なら、山1つあたりちょうど1時間です。したがって、速度は最大の山である30を1時間で食べきれる必要があります。速度が29だと、その山を食べるのにもう1時間必要になります。
- 入力
- piles = [5, 9, 2]h = 20
- 出力
- 1
- 説明
- 速度1では、山を食べるのに5 + 9 + 2 = 16時間かかり、20時間以内に十分収まります。1より遅い速度はないため、答えは1です。
発展問題
Twin問題：Kokoは1日に最大k本のバナナを食べ、d日以内に、山を順番に丸ごと食べます。最小のkはいくつで、探索では何が変わりますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
速度
kを1つ固定します。ココは1時間の途中で食べる山を切り替えないとすると、その速度でp本のバナナの山を食べるのに何時間かかりますか？すべての山を食べるには何時間かかりますか？速度
kで時間内に終わるなら、それより速い速度でもすべて時間内に終わります。条件を満たす速度は、答えとなる速度から始まる途切れのない連続した範囲を形成します。速度の範囲を1から最大の山までとして二分探索します。1回の走査で中央の速度で必要な時間数を数えます。
h以内に収まれば、答えは中央以下です。そうでなければ、中央より大きくなります。
解説
答えは配列内の位置ではなく速度です。ここに二分探索のヒントがあります。速度を1つ調べるには、山を一度走査します。速度 k で制限時間内に終わるなら、それより速い速度でもすべて間に合います。そこで、速度を1から最も大きな山の数まで二分探索します。最大10億回の代わりに、チェック回数は約30回です。
1から順にすべての速度を試す
正しいが、最大のテストでは終わらない
考え方
Kokoは1時間の間に別の山へ移動しないため、p本のバナナの山を食べるには、p / k時間を切り上げた時間がかかります。速度4なら、10本を食べるのに3時間かかります。速度を1、2、3……と試し、合計時間がh以内に収まる最初の速度を返します。これが最小の速度です。それより遅い速度はすべて条件を満たさず、ループは最大の山の速度で止まります。この速度なら、各山にかかる時間は1時間です。
最大の山をmとすると、n個の山について最大m回の確認が必要です。5000個の山がそれぞれ10^9近くで、h = 5000の場合、約5 × 10^12ステップになります。
アルゴリズム
speed = 1に設定します。- この速度でかかる時間を数えます。各山について
(pile + speed-1) / speedを加算し、合計には64ビット整数を使用します。 - 合計が
h以下なら、speedを返します。 - そうでなければ、
speedに1を加えて、もう一度数えます。
def minEatingSpeed(piles, h):
speed = 1
while True:
hours = 0
for pile in piles:
hours += (pile + speed - 1) // speed # a started pile costs a whole hour
if hours <= h:
return speed
speed += 1速度に対する二分探索
考え方
速度が上がるほど、各山にかかる時間は同じかそれ以下になるため、「この速度なら時間内に終わるか？」への答えは、最初の「はい」以降、「いいえ、いいえ、いいえ、はい」となります。二分探索で最初の「はい」を見つけます。
答えが常に範囲内に含まれるように、loからhiまでの範囲を保ちます。最初は1から最大の山の大きさまでとします。最大の山の大きさの速度なら、各山に1時間かかるため、制限時間内に収まります。中央の速度midで間に合う場合、答えはmidかそれより遅い速度なので、hi = midとします。間に合わない場合、それより遅い速度もすべて間に合わないため、lo = mid + 1とします。loとhiが一致したとき、それが答えです。
最初の例では、範囲は1から10で始まります。速度5なら間に合うため、範囲は1から5になります。速度3では10時間かかるため、範囲は4から5になります。速度4では7時間かかるため、範囲は5から5になります。
アルゴリズム
lo = 1に設定し、hiを最大の山の大きさに設定します。lo < hiの間、mid = lo + (hi - lo) / 2を求めます。- 速度
midで必要な時間を数えます。各山について(pile + mid-1) / midを加算し、合計は64ビット整数で保持します。 - 合計が
h以下なら、hi = midに設定します。それ以外の場合は、lo = mid + 1に設定します。 loを返します。
def minEatingSpeed(piles, h):
lo, hi = 1, max(piles) # the largest pile always works: one hour per pile
while lo < hi:
mid = lo + (hi - lo) // 2
hours = 0
for pile in piles:
hours += (pile + mid - 1) // mid
if hours <= h:
hi = mid # mid works, so the answer is mid or slower
else:
lo = mid + 1 # mid is too slow, so the answer is faster
return lo
落とし穴と境界ケース
- 時間数のオーバーフロー。速度が 1 のとき、
10^9個のバナナの山が 5000 個あると、所要時間は5 × 10^12時間となり、32 ビットの上限を超えます。合計がオーバーフローすると、遅い速度でも条件を満たしてしまうことがあります。64 ビット整数で数えるか、合計がhを超えた時点で処理を止めましょう。 - 切り捨て。
10 / 4は 2 になりますが、その山を食べるには 3 時間かかります。 - 範囲を 0 から始めること。すると
midが 0 になり、カウントの計算でゼロ除算が発生する可能性があります。 midが条件を満たすときにhi = mid - 1を設定すること。これにより答えを範囲から除外してしまう可能性があります。- 最大の山より小さい値を
hiに設定すること。hが山の数と等しい場合、より遅い速度はすべて条件を満たさず、探索結果としてそのうちの 1 つが返されます。
よくある質問3
ココがバナナを食べる問題の時間計算量はどれくらいですか？
二分探索の実行時間はO(n log m)で、nは山の数、mは最大の山の大きさです。必要なチェック回数は約log2(m)回で、m = 10^9の場合は30回です。各チェックではすべての山を1回ずつ調べます。追加の空間計算量はO(1)です。
速度の下限と上限はいくつですか？
上限は最も大きな山です。そこではすべての山を食べるのに1時間かかり、必ず間に合います。下限は1で、ココは1時間に最大k本のバナナを食べるため、バナナの総数をhで割って切り上げた値まで引き上げることができます。
整数で割り算をして切り上げるにはどうすればよいですか？
整数除算で (p + k-1) / k を使います。k-1 を加えると、余りが次の k の倍数を超える位置に押し上げられ、ちょうど倍数の場合はそのままです。速度が 4 のとき、10 なら 13 / 4 = 3、8 なら 11 / 4 = 2 になります。浮動小数点数は必要ありません。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def minEatingSpeed(piles, h):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
piles = [4, 10, 7, 3] h = 6
期待される出力
5