Koko Eating Bananas
Kokoはn個のバナナの山を持っています。ここで、piles[i]は山iにあるバナナの数で、警備員が戻ってくるまであとh時間あります。彼女は1時間あたりに食べるバナナの数である整数の速度kを1つ選び、その速度を変えません。1時間ごとに、1つの山からk個のバナナを食べます。その山に残っているバナナがk個未満の場合は、その山を食べ終え、時間が終わるまで休みます。h時間以内にすべての山を食べ終えられる最小の速度kを返してください。
関数
- pilesinteger-array
- 各山にあるバナナの数
- hinteger
- Kokoが持っている時間数
- 戻り値integer
- h時間以内にすべての山を食べ終えられる、1時間あたりのバナナ数で表した最小の整数の食べる速度
制約
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時間となるため、1時間超過します。
- 入力
- 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です。
提出時に隠しテスト+22件
発展問題
対になる問題：Kokoにはd日あり、与えられた順番に山を丸ごと食べていきます。1日の上限であるk本のバナナに収まる限り、1日にできるだけ多くの山を食べます。最小のkはいくつでしょうか。また、二分探索のどの2つの部分が変わるでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
速度
kを1つ決めます。ココが1時間の間に食べる山を切り替えないとすると、p本のバナナの山をその速度で食べるのに何時間かかりますか？すべての山を食べるには何時間かかりますか？速度
kで時間内に完了できるなら、それより速い速度でもすべて時間内に完了できます。条件を満たす速度は、答えとなる速度から始まる途切れのない範囲を形成します。速度の範囲を1から最大の山の大きさまでとして二分探索します。1回の走査で中間の速度における時間数を数えます。
h時間以内に収まれば、答えは中間以下です。そうでなければ、中間より大きくなります。
解説
ここでの答えは配列内の位置ではなく速度なので、二分探索だと気づきにくくなっています。速度を1つ調べるには、山を一巡するだけです。また、判定結果は順序に沿っています。速度 k で時間内に終わるなら、それより速い速度でもすべて時間内に終わります。したがって、速度1から最も大きな山までを二分探索すればよく、必要な判定は約30回です。速度を1つずつ試す場合は、10億回必要になることもあります。
1から順にすべての速度を試す
正しいが、最大のテストでは終わらない
考え方
まず、1つの問いから始めましょう。p本のバナナの山を、速度kで食べるにはどれくらいかかるでしょうか？ココは1時間にk本食べ、同じ1時間のうちに別の山へ移ることはないので、その山を食べるのにかかる時間はp / k時間を切り上げた値です。速度4なら、10本の山を食べるのに3時間かかります。4本、4本、そして2本食べて、残りの時間は休みます。すべての山について合計し、その合計をhと比べましょう。
次に、速度を1、2、3、……の順に試し、合計がh以内に収まる最初の速度を返します。より遅い速度はすべて試して失敗しているため、構造上、これは最小の速度です。ループは必ず停止します。最大の山の本数と同じ速度なら、各山を食べるのに1時間かかり、hは山の数以上だからです。
問題は、ループがどれだけ長く続くかです。ほぼ10^9本のバナナがある山が5000個あり、h = 5000の場合、答えは10^9に近くなります。そのため、ループは約10億回実行され、各チェックで5000個すべての山を調べます。つまり、約5 × 10^12ステップです。ここでmは最大の山の本数です。
アルゴリズム
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速度に対する二分探索
考え方
速度 1 から最大の山の大きさまでの各速度を、「この速度なら時間内に終わるか？」という問いへの答えの列として考えてみましょう。速度が上がるにつれて、各山を食べるのにかかる時間は同じか短くなるため、合計時間が増えることはありません。そのため、この列は「いいえ」が続いた後、最初の「はい」から最後まで「はい」が続き、途中で「いいえ」に戻ることはありません。探しているのは最初の「はい」です。「いいえ」と「はい」が並ぶこの列は、まさに二分探索で半分ずつに分ける対象です。
答えを常に含む範囲 lo から hi を保ちます。範囲は 1 から最大の山の大きさで始めます。最大の山の大きさの速度なら各山に 1 時間かかり、h はその時間をまかなえるので、この範囲で問題ありません。中央の速度 mid を調べます。時間内に終わるなら、答えは mid 以下の速度なので、hi = mid として mid を範囲に残します。時間内に終わらないなら、それより遅い速度もすべて間に合わないので、lo = mid + 1 とします。lo と hi が一致したら、その速度が答えです。
最初の例、山の大きさが 4、10、7、3 で、h = 6 の場合を追ってみましょう。範囲は 1 から 10 です。速度 5 では 1 + 2 + 2 + 1 = 6 時間かかり、条件を満たすため、範囲は 1 から 5 になります。速度 3 では 2 + 4 + 3 + 1 = 10 時間かかり、時間がかかりすぎるため、範囲は 4 から 5 になります。速度 4 では 1 + 3 + 2 + 1 = 7 時間かかり、まだ時間がかかりすぎるため、範囲は 5 から 5 になり、答えは 5 です。
各確認で範囲が半分になるため、最大 10^9 個の速度を含む範囲でも、必要な確認は約 30 回です。1 回の確認につき山が 5000 個ある場合でも、数兆回ではなく約 150000 回の処理で済みます。
アルゴリズム
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ビット整数の上限である約2.1 × 10^9を大きく超えます。合計値がオーバーフローすると小さな値になり、遅すぎる速度でも条件を満たすと判定されることがあります。64ビット整数で数えるか、合計がhを超えた時点で数えるのをやめましょう。 - 切り上げる方向を間違える。整数除算は切り捨てるため、
10 / 4は2になりますが、その山を食べるには3時間かかります。(pile + k-1) / kを使って切り上げましょう。 - 範囲を0から始める。その場合、
midが0になり、所要時間の計算でゼロ除算が発生することがあります。実際に取りうる最も遅い速度は1です。 midが条件を満たすときにhiをmid - 1にする。これでは答えそのものを範囲から除外してしまうことがあります。条件を満たす最初の速度を探す場合は、hi = midとしてmidを範囲に残し、lo < hiの間ループしましょう。hiを最大の山より小さく設定する。hが山の数と等しい場合、それより遅い速度はすべて条件を満たさないことがあるため、探索結果として条件を満たさない速度が返されてしまいます。
よくある質問4
バナナを食べるココの時間計算量はどれくらいですか？
二分探索の実行時間は O(n log m) です。ここで、n は山の数、m は最大の山の大きさです。各チェックではすべての山を1回ずつ調べ、速度の範囲はチェックごとに半分になるため、チェック回数は約 log2(m) 回です。m = 10^9 の場合は30回です。追加の空間計算量は O(1) です。
なぜ二分探索は食べる速度の問題で使えるのでしょうか？
二分探索には、答えが順序付けられる「はい」か「いいえ」で答えられる質問が必要です。「Koko は速度 k で終えられるか？」がその一例です。速度が速くなっても必要な時間は増えません。各山について、p / k を切り上げた値は、k が大きくなるにつれて小さくなる一方だからです。したがって、答えより遅い速度ではすべて失敗し、答え以上の速度ではすべて成功するため、探索で境界を見つけられます。
速度の下限と上限はいくつですか？
上限は最も大きな山の数です。その速度なら各山をちょうど1時間で食べ終えられ、hは山の数以上なので、必ず間に合います。さらに速い速度でも山ごとに1時間は必要なので、それより上を探索しても意味がありません。下限は1です。また、ココが1時間に食べるバナナは最大でもk本なので、バナナの総数をhで割って切り上げた値まで下限を引き上げられます。
整数を使って割り算し、切り上げるにはどうすればよいですか？
整数除算で (p + k-1) / k を使います。k-1 を加えると、余りがあれば次の k の倍数まで繰り上がり、ちょうど割り切れる場合はそのままです。速度 4 で 10 の場合は 13 / 4 = 3、速度 4 で 8 の場合は 11 / 4 = 2 となります。これにより、大きな値が誤った方向に丸められることのある浮動小数点演算を避けられます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def minEatingSpeed(piles, h):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
piles = [4, 10, 7, 3] h = 6
期待値
5