概要

本を番号順に左から詰めて本棚の段に並べていくシミュレーション問題です。段の横幅 \(W\) を超えそうになったら次の段に移り、最終的に必要な段数を求めます。

考察

この問題はルールが明確に定められたシミュレーション問題です。本を1冊ずつ順番に処理し、現在の段に入るかどうかを判定するだけで解けます。

具体例で理解する：

例えば \(W = 10\)、本の厚さが \([3, 4, 2, 5, 3]\) の場合を考えます。

• 1冊目（厚さ3）: 段1の最初の本。段1の幅 = \(3\)
• 2冊目（厚さ4）: \(3 + 1 + 4 = 8 \leq 10\) → 段1に収まる。段1の幅 = \(8\)
• 3冊目（厚さ2）: \(8 + 1 + 2 = 11 > 10\) → はみ出す！段2に移る。段2の幅 = \(2\)
• 4冊目（厚さ5）: \(2 + 1 + 5 = 8 \leq 10\) → 段2に収まる。段2の幅 = \(8\)
• 5冊目（厚さ3）: \(8 + 1 + 3 = 12 > 10\) → はみ出す！段3に移る。段3の幅 = \(3\)

答えは 3段 です。

素朴なアプローチで十分か？

\(N\) が最大 \(10^6\) ですが、各本に対して \(O(1)\) の判定を行うだけなので、全体 \(O(N)\) で十分間に合います。特別なアルゴリズムは不要で、問題文のルールをそのまま実装すれば正解できます。

ただし、Pythonでは入力処理が遅いと TLE になる可能性があるため、sys.stdin.buffer.read() でまとめて読み込む工夫が必要です。

アルゴリズム

1. 段数 shelves を \(1\)、現在の段の使用幅 current_width を \(0\) で初期化する。
2. 本を \(1\) 冊目から \(N\) 冊目まで順に処理する：
   • 現在の段に本がない（current_width == 0）なら、その本を置く：current_width = L
   • 現在の段に本がある場合：
     • current_width + 1 + L ≤ W なら同じ段に追加：current_width += 1 + L
     • そうでなければ次の段に移る：shelves += 1、current_width = L
3. 最終的な shelves を出力する。

計算量

• 時間計算量: \(O(N)\) — 各本を1回ずつ処理するだけ
• 空間計算量: \(O(N)\) — 入力データの読み込みに使用（オンラインで1冊ずつ読めば \(O(1)\) も可能）

実装のポイント

• 高速な入力処理: \(N\) が最大 \(10^6\) のため、Pythonでは sys.stdin.buffer.read() で一括読み込みし、split() でトークンに分割する方法が高速です。input() を \(N\) 回呼ぶと TLE になりやすいです。

• 初期値の設定: 段数は最初から \(1\) としておき、段が溢れるたびにインクリメントします。current_width = 0 で始めることで、最初の本を置くときも「本がまだない段」として統一的に扱えます。

• 仕切り板の扱い: 仕切り板（隙間 \(1\) cm）は本と本の間にのみ入ります。段の最初の本の前には不要なので、current_width == 0 の場合を分けて処理しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    W = int(input_data[1])
    
    shelves = 1
    current_width = 0
    
    for i in range(N):
        L = int(input_data[i + 2])
        if current_width == 0:
            current_width = L
        elif current_width + 1 + L <= W:
            current_width += 1 + L
        else:
            shelves += 1
            current_width = L
    
    print(shelves)

main()

この解説は claude4.6opus-thinking によって生成されました。