コンテンツにスキップ

DOJ Beginner Contest 13 B - Chronicler

サイト
DOJ
コンテスト
DOJ Beginner Contest 13
問題
B - Chronicler

NN 日分の竹簡があり、ii 日目の竹簡は AiA_i 枚です。これを 1 日目から順に、容量 KK の本に綴じていきます。1 日分の竹簡は分けられません。今の本にその日の竹簡を加えて KK 枚以下なら今の本に綴じ、KK 枚を超えるなら次の本にその日の竹簡をすべて綴じます。本の冊数が MM 冊以下になる最小の KK を求める問題です(1≤M≤N≤10001 \le M \le N \le 1000、1≤Ai≤1001 \le A_i \le 100、∑Ai≤10000\sum A_i \le 10000)。

1 日分の竹簡が 1 冊に収まらないといけないので、K≥max⁡AK \ge \max A です。また K=∑AK = \sum A なら全部が 1 冊に収まるので、条件を満たします。

そこで KK を max⁡A\max A から ∑A\sum A まで小さい順に試し、それぞれについて問題文の規則どおりに本を綴じて冊数を数えます。冊数が初めて MM 以下になった KK が答えです。

試す KK は ∑A≤10000\sum A \le 10000 通り以下で、1 回のシミュレーションは O(N)O(N) なので、全体で O(N∑A)O(N \sum A)、最大 10710^7 回程度です。

なお、KK を大きくしても冊数は増えないので、KK を二分探索すれば O(Nlog⁡∑A)O(N \log \sum A) でも求まります。

Python
N, M = map(int, input().split())
A = list(map(int, input().split()))
for k in range(max(A), sum(A) + 1):
t = 0
f = 1
for a in A:
if t + a > k:
f += 1
t = a
else:
t += a
if f <= M:
print(k)
break

t が今の本に綴じた竹簡の枚数、f が冊数です。