問題
試験のpages と、hours (何時間かk ページとhours 時間以内にk を
- 1 時間ごとに、
読み終えていない本を 1 冊選び、 その本を 最大 kページ読みます - 選んだ本の
残りが kページより少なければ、 その本を 読み終えて、 その 1 時間の 残りは 休みます (別の 本には 移りません) kは 1 以上の整数ですpagesの長さは 1 以上 10000 以下で、 hoursはpagesの長さ以上 10 億以下です (1 冊に 1 時間かければ、 いつかは 必ず読み切れます) - 各本の
ページ数は 1 以上 10 億以下です
入力と出力の例
例 1
k が 7 なら、k が 6 だと 7 時間かかり、
入力
pages = [9, 4, 12, 7]
hours = 6出力
7例 2
時間が
入力
pages = [15, 15, 15]
hours = 3出力
15例 3
1 冊を 7 時間で
入力
pages = [100]
hours = 7出力
15面接での聞かれ方
面接では、
- 「締め切りに
間に 合う、 いちばん遅い 速さを 求めてください」 - 「速さを 1 から
順に 試すと、 どれくらい かかりますか？」と、 素直な 書き方の 重さを 先に 聞かれる ことがあります - 書き終えた
あとに 「二分探索の 範囲の 上と 下は、 なぜ その値ですか？」 「間に 合うか どうかが、 なぜ速さに ついて 単調なのですか？」と、 二分探索を 使って よい 理由を 聞かれます - 同じ型の
問題として、 「d 日で 荷物を 運び切れる、 船の 最小の 積める 量」などが 続けて 出る こともあります
ミドルの
アルゴリズムのチートシートの「ソートと二分探索」に、この型の要点を表とコードでまとめています。
まず
段 1
まずは、k を 1 つk で
段 2
素直には、k を 1 から 1 つずつhours 以内に
段 3
速さを
段 4
範囲 [lo, hi] のmid でmid か、hi = mid にします (mid をmid よりlo = mid + 1 にします。lo と hi が
解答
Python
Python
def min_reading_speed(
pages, hours
):
lo, hi = 1, max(pages)
while lo < hi:
mid = (lo + hi) // 2
need = 0
for p in pages:
t = p + mid - 1
need += t // mid
if need <= hours:
hi = mid
else:
lo = mid + 1
return loJavaScript
JavaScript
function minReadingSpeed(
pages, hours
) {
let lo = 1;
let hi = Math.max(...pages);
while (lo < hi) {
const mid = Math.floor(
(lo + hi) / 2
);
let need = 0;
for (const p of pages) {
need += Math.ceil(
p / mid
);
}
if (need <= hours) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}Go
Go
func minReadingSpeed(
pages []int, hours int,
) int {
lo, hi := 1, 0
for _, p := range pages {
hi = max(hi, p)
}
for lo < hi {
mid := (lo + hi) / 2
need := 0
for _, p := range pages {
t := p + mid - 1
need += t / mid
}
if need <= hours {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}Python と Go の t は、p + mid - 1 を mid でp を mid でMath.ceil を
計算量
- 時間は O(n log m) です。
n は 本の 冊数、 m は いちばん厚い本の ページ数です。 範囲を 半分ずつ絞るので、 試す回数は log m 回 (10 億でも 約 30 回) で、 1 回ごとに n 冊を数えます - 使う
記憶は O(1) です。 範囲の 両端と、 時間を 足す置き場だけです - かかる
時間の 合計は、 最大で 10000 冊 × 10 億時間で 10 兆に なります。 Go の int(64 ビット) と JavaScript の数 (約 9000 兆まで 正確) で 収まります。 32 ビットの 整数で 数える 言語では、 あふれに 気をつけます
よく
- 間に
合った ときに hi = mid - 1にする。midそのものが 答えの こともあるので、 捨ててしまいます。 例 3 では、 15 で 間に 合った ときに 上を 14 に すると、 答えの 15 が 範囲から 外れ、 1 つずれた 答えになります - 切り上げずに割る。
p // midだと、9 ページを 7 ずつ 読むのが 1 時間と 数えられ、 かかる 時間を 少なく 見積もって、 遅すぎる 速さを返します - 範囲の
下を 0 にする。 midが 0 になると、 0 で 割って 止まります。 速さは 1 以上 なので、 下は 1 です - 上を
ページ数の 合計にする。 間違いでは ありませんが、 範囲が 広がるだけです。 いちばん厚い本の ページ数で 十分だと、 理由と 一緒に 言えると 評価が 上がります - 合計を 32 ビットの
整数で数える。 時間の 合計は 10 兆まで 届くので、 あふれて 負の 数に なり、 間に 合うと 取り違えます
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「速さを 1 から
順に 試すと、 最大で 10 億回それぞれ O(n) かかります。 速さを 上げると かかる 時間は 増えないので、 間に 合うか どうかは、 ある 速さを 境に 分かれます。 だから 答えの 値の 範囲、 1 から いちばん厚い本の ページ数までを 二分 探索します。 1 回ごとに 切り上げの 割り算で 時間を 数えるので、 全体で O(n log m)、 記憶は O(1) です。」
書き終えたら、
「例 1 で
たどります。 範囲は 1 から 12 です。 真ん中の 6 では 7 時間かかって間に 合わないので、 下を 7 にします。 7 から 12 の 真ん中の 9 では 5 時間で 間に 合うので、 上を 9 にします。 7 から 9 の 真ん中の 8 も 6 時間で 間に 合うので 上を 8 にし、 7 と 8 の 真ん中の 7 は 6 時間で 間に 合うので 上を 7 にします。 上と 下が 7 で 重なり、 7 を 返します。」