Book Allocation Problem
棚には本が決まった順序で並んでおり、pages[i] は本 i のページ数です。本を students 人の学生に分けます。各学生は隣り合う本を連続して、少なくとも1冊ずつ受け取り、すべての本はちょうど1人の学生に割り当てられます。学生の負荷は、受け取った本のページ数の合計です。
最も負荷の大きい学生の負荷として可能な最小値を返してください。学生の人数が本の冊数より多い場合は、-1 を返してください。
関数
- pagesinteger-array
- 棚の並び順で各本のページ数
- studentsinteger
- 本を共有する生徒の数
- 戻り値integer
- 可能な限り小さい最大負荷、または生徒数が本の数を上回る場合は -1
制約
1 ≤ pages.length ≤ 50001 ≤ pages[i] ≤ 1051 ≤ students ≤ 104-
students > pages.lengthの場合は-1を返します。
例
- 入力
- pages = [25, 40, 15, 30, 50]students = 3
- 出力
- 65
- 説明
[25, 40]、[15, 30]、[50]を配ると、合計はそれぞれ65、45、50です。上限を64にすると失敗します。配分結果は[25]、[40, 15]、[30]、[50]となり、4人になります。
- 入力
- pages = [10, 20]students = 3
- 出力
- -1
- 説明
- 本が2冊では、3人の生徒に1人1冊ずつ渡せないので、答えは
-1です。
- 入力
- pages = [7, 3, 9]students = 3
- 出力
- 9
- 説明
- 3冊の本と3人の生徒がいて、生徒1人につき本を1冊ずつ渡します。最も重いのは9ページの本です。
発展問題
切り上げた平均冊数に最も厚い本を足した数が、常に有効な上限であることを証明してください。薄い本が並ぶ棚では、この上限によって確認回数をどれだけ減らせますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
最適な切り方を探す代わりに、ページ数の上限を決めましょう。誰もその上限を超えて持てない場合、何人の生徒が必要ですか？
本を棚の順番どおりに配り、次の本が上限を超える場合にのみ、次の生徒に移ります。上限を高くしても、必要な生徒数が増えることはありません。
学生の数が本の数を上回る場合は
-1を返します。それ以外の場合は、最も厚い本のページ数と平均配分の大きい方から合計までの範囲で、上限を二分探索します。
解説
棚を分割する方法は多すぎますが、ページ数の上限を1つ試すのは簡単です。棚の順に本を配り、本を渡すと上限を超える場合は次の生徒に移り、生徒の数を数えます。上限を高くしても必要な生徒数が増えることはないので、条件を満たす上限は連続した範囲になり、その範囲の開始位置は二分探索で見つけられます。
ページ上限を1ページずつ引き上げる
正しいが、最大のテストでは終わらない
考え方
L = max(pages)から始めます。最も厚い本を持つ人がいるためです。そして、貪欲法で数えた人数がstudentsに収まるまで、Lを1ページずつ増やします。それより小さい上限はすべて条件を満たさなかったので、最初に条件を満たす値が答えです。最初の例では、50から64までの上限ではどれも4人必要で、65では3人になります。確認回数は16回です。
答えは棚全体のページ数になることもあります。たとえば、1人の学生が10^5ページの本を5000冊担当する場合、上限の候補は約5 × 10^8個あり、それぞれで5000冊を一巡します。時間の列では、Aは答え、mは最も厚い本を表します。
アルゴリズム
students > pages.lengthの場合は、-1を返します。- 上限
Lに対する貪欲法での人数を求めます。生徒1人、負荷0から始めます。load + pages[i] > Lの場合は生徒を1人追加し、負荷をpages[i]に設定します。それ以外の場合は、その本を負荷に加えます。 Lを最も厚い本に設定します。Lに対する人数がstudentsより多い間、Lに1を加えます。Lを返します。
def studentsNeeded(pages, limit):
count, load = 1, 0 # the first student starts with no pages
for p in pages:
if load + p > limit:
count += 1 # this book opens the next student's block
load = p
else:
load += p
return count
def allocateBooks(pages, students):
if students > len(pages):
return -1 # someone would get no book
limit = max(pages) # the thickest book has to fit somewhere
while studentsNeeded(pages, limit) > students:
limit += 1
return limitページ制限に対する二分探索
考え方
貪欲法での人数は、Lの条件で本を分担する場合に必要となる学生数の最小値です。ほかのどの分担方法と比べても、学生ごとに見ると、貪欲法では次の本が収まらなくなった時点でのみ学生を切り替えるため、少なくとも同じだけ本棚の先まで進みます。学生数が実際より少なくても問題ありません。2冊持っている学生から1冊を、1冊も持っていない学生に渡せばよく、誰の負担も増えません。
したがって、貪欲法での人数がstudents以下の場合に限り、Lで分担できます。Lで分担できるなら、L+1でも分担できます。そのため、二分探索で分担可能な最初の上限を見つけられます。
探索範囲の下限は、max(pages)と平均の取り分であるtotal / studentsを切り上げた値のうち、大きい方です。最も大きい負担はこの両方以上になるためです。上限はtotalです。最初の例では範囲は54から160で、探索では107、80、67、60、64、66、65を試します。
アルゴリズム
students > pages.lengthの場合は、-1を返します。totalを合計し、最も厚い本を見つけます。loを、最も厚い本と(total + students - 1) / studentsの大きい方に設定し、hi = totalとします。lo < hiの間、mid = lo + (hi - lo) / 2を求めます。midに対して貪欲法で数を数えます。それがstudents以下なら、hi = midに設定します。そうでなければ、lo = mid + 1に設定します。loを返します。
def studentsNeeded(pages, limit):
count, load = 1, 0 # the first student starts with no pages
for p in pages:
if load + p > limit:
count += 1 # this book opens the next student's block
load = p
else:
load += p
return count
def allocateBooks(pages, students):
if students > len(pages):
return -1 # someone would get no book
total = sum(pages)
# no limit can be below the thickest book or below the average share
lo = max(max(pages), (total + students - 1) // students)
hi = total # one student could carry the whole shelf
while lo < hi:
mid = lo + (hi - lo) // 2
if studentsNeeded(pages, mid) <= students:
hi = mid # mid is enough, so the answer is mid or lower
else:
lo = mid + 1 # mid needs too many students
return lo
落とし穴と境界ケース
-1のチェックを省略すること。[10, 20]と学生3人の場合、上限を20とすると貪欲法で数えた人数は2となるため、探索結果は20になります。- 範囲を平均配分だけを基準にして開始すること。
[1, 9]と学生2人の場合、平均は5です。このとき貪欲法では9ページの本を1人に割り当て、人数は2となるため、結果は5になります。 studentsと完全に一致するかを確認すること。[5, 5, 5, 5, 5, 5]と学生4人の場合、答えは10で、このとき貪欲法で数えた人数は3です。- 本をソートすること。
[10, 1, 1, 10]を学生2人に割り当てると11になりますが、[1, 1, 10, 10]にソートすると12になります。
よくある質問3
書籍割り当て問題は、分割配列最大和問題と同じですか？
はい。どちらも配列を、空でない連続したブロックに固定数だけ分割し、最大のブロック和を最小化します。同じ二分探索と貪欲法による判定で、どちらも解けます。書籍版では-1の場合が追加されています。
書籍割り当て問題の時間計算量は何ですか？
時間計算量は O(n log S)、追加の領域計算量は O(1) です。ここで、n は本の数、S は総ページ数です。試す各上限につき、本を1回走査し、探索では約 log2 S 個の上限を試します。5 × 10^8 ページの棚なら29個です。
本を割り当てることが不可能なのはどのような場合ですか？
生徒の人数が本の数より多い場合に限ります。すべての生徒に少なくとも1冊の本が必要だからです。本が十分にあれば、2冊以上の本のまとまりから最後の1冊を本を持っていない生徒に渡すことができ、全員が1冊ずつ持つまでそれを続けられます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def allocateBooks(pages, students):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
pages = [25, 40, 15, 30, 50] students = 3
期待される出力
65