概要

本棚の段ごとの横幅制限に注意しながら、本を順番に並べていき、必要な段数を求めます。

考察

この問題は、貪欲法（greedy）によって効率的に解くことができます。

重要なポイントは「現在の段に次の本を置けるかどうか」を判定する条件です。
すでに本が置かれている段にさらに本を置くには、間に1cmの隙間が必要なので、
「現在の段の使用幅 \(+\) 1（隙間）\(+\) 次の本の厚さ」が段の幅 \(W\) 以内に収まる必要があります。

つまり、 - 現在の段の使用幅が \(0\) のときは、無条件に次の本を置ける。 - そうでないときは、\(current\_width + 1 + L[i] \leq W\) なら同じ段に、超えるなら次の段に置く。

素朴なアプローチとして、実際に本を2次元的に管理してシミュレーションする方法が考えられますが、 本の冊数 \(N\) が最大 \(10^6\)、段の幅 \(W\) が最大 \(10^9\) であるため、 メモリや計算時間の観点から非現実的です。

そこで、「現在の段の使用幅」と「使用中の段数」だけを管理することで、 すべての本を順番に処理しながら必要な段数を数えることができます。

アルゴリズム

1. 変数 shelves（使用中の段数）を初期値 \(1\) に設定。
2. 変数 current_width（現在の段に使われている幅）を初期値 \(0\) に設定。
3. 各本 \(L_i\) に対して以下の処理を行う：
   • もし current_width == 0 なら、その本を現在の段の先頭に置く（隙間は不要）。
     • current_width += L[i]
   • それ以外の場合：
     • current_width + 1 + L[i] <= W なら、同じ段に置く。

          - `current_width += 1 + L[i]`
       

     • そうでないなら、新しい段に移動。

          - `shelves += 1`
          - `current_width = L[i]`
       

4. 最終的な shelves の値を出力。

例

入力:

5 10
3 4 2 1 5

処理の流れ: - 最初の段に 3cm の本を置く → 幅: 3 - 次の本 4cm → 3 + 1 + 4 = 8（OK）→ 幅: 8 - 次の本 2cm → 8 + 1 + 2 = 11（NG）→ 新しい段に移動、幅: 2 - 次の本 1cm → 2 + 1 + 1 = 4（OK）→ 幅: 4 - 次の本 5cm → 4 + 1 + 5 = 10（OK）→ 幅: 10

合計段数: 2

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) （入力の配列を除く）

実装のポイント

• 「現在の段の使用幅」を正確に管理すること。
• 最初の本は隙間なしで置ける点に注意。
• 条件分岐を正しく行い、新しい段に移るタイミングで current_width をリセットすること。

## ソースコード

```python
N, W = map(int, input().split())
L = list(map(int, input().split()))

shelves = 1
current_width = 0

for i in range(N):
    if current_width == 0:
        current_width += L[i]
    else:
        if current_width + 1 + L[i] <= W:
            current_width += 1 + L[i]
        else:
            shelves += 1
            current_width = L[i]

print(shelves)

---

この解説は qwen3-coder-480b によって生成されました。