概要

本を番号順に左から詰めて並べ、幅 \(W\) を超えそうなら次の段に移る、というルールで並べたときに必要な段数を数える問題です。

考察

重要なのは「並べ方が固定（貪欲に順番通り詰める）で、段数はシミュレーションすれば一意に決まる」点です。
つまり、各段について「いま段に置いている合計幅」を持っておき、次の本を置けるかどうかを判定していけば十分です。

• 現在の段が空なら、その本は必ず左端に置ける（\(L_i \le W\) が保証）。
• 空でないなら、必要な追加幅は「仕切りの \(1\) cm + 本の厚さ \(L_i\)」。
  • \(cur + 1 + L_i \le W\) なら同じ段に置く
  • 超えるなら段を増やして新しい段で置く

素朴に「段ごとに配列を作って本を詰める」「段の中身を保持する」などをすると、管理が重くなるうえに本が最大 \(10^6\) 冊なので、入出力が遅いとTLEになりやすいです。
解決策は「必要なのは合計幅 \(cur\) と段数 \(rows\) だけ」と割り切って \(O(N)\) で一気に処理し、入力も高速に読むことです。

具体例：\(W=10\), 本が \([4,3,3]\) のとき
- 1冊目: 空なので \(cur=4\)
- 2冊目: \(4+1+3=8 \le 10\) なので同じ段、\(cur=8\)
- 3冊目: \(8+1+3=12 > 10\) なので次の段、段数 \(+1\)、新段で \(cur=3\)
→ 段数は \(2\)

アルゴリズム

1. 段数 \(rows=1\)、現在の段の使用幅 \(cur=0\) で開始する。
2. 本を \(i=1..N\) の順に読む。
3. もし \(cur=0\)（段が空）なら \(cur=L_i\)。
4. そうでなければ、\(cur + 1 + L_i \le W\) を満たすか判定する。
   • 満たすなら \(cur \leftarrow cur + 1 + L_i\)
   • 満たさないなら \(rows \leftarrow rows + 1\)、\(cur \leftarrow L_i\)
5. 最後に \(rows\) を出力する。

計算量

• 時間計算量: \(O(N)\)（各本につき一定回の比較と加算）
• 空間計算量: \(O(1)\)（合計幅と段数のみ）

実装のポイント

• \(N\) が最大 \(10^6\) なので、Pythonでは input() を繰り返すより sys.stdin.buffer.read() でまとめて読み、整数を高速パースすると安全です（提示コードの next_int()）。

• 「段が空かどうか」で場合分けすると、先頭の本に余計な仕切り \(1\) を足してしまうミスを防げます。

• 各 \(L_i \le W\) が保証されているため、「新しい段に移っても置けない」ケースを考える必要はありません。

  ソースコード

import sys

data = sys.stdin.buffer.read()
n = len(data)
idx = 0

def next_int():
    global idx
    while idx < n and data[idx] <= 32:
        idx += 1
    num = 0
    while idx < n and data[idx] > 32:
        num = num * 10 + (data[idx] - 48)
        idx += 1
    return num

N = next_int()
W = next_int()

rows = 1
cur = 0

for _ in range(N):
    L = next_int()
    if cur == 0:
        cur = L
    else:
        if cur + 1 + L <= W:
            cur += 1 + L
        else:
            rows += 1
            cur = L

sys.stdout.write(str(rows))

この解説は gpt-5.2-high によって生成されました。