概要

この問題は、与えられた \(N\) 冊の本を、決まったルール（厚さと隙間の合計が \(W\) を超えないように配置する）に従って順番に並べたとき、最終的に何段の本棚が必要になるかを求めるシミュレーション問題です。

考察

この問題の最も重要な点は、「本の順番を入れ替えてはいけない」ことと、「各段にできるだけ多くの本を詰め込むのが最適である」という点です。

本を順番に見ていき、現在の段に収まるならそのまま配置し、収まらないなら新しい段を用意するという「貪欲法（Greedy Algorithm）」の考え方で解くことができます。

具体的なシミュレーションの例

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

1. 1冊目 (4cm): 1段目の左端に置きます。現在の幅 = \(4\)
2. 2冊目 (3cm): 1段目に「隙間 \(1\) + 厚さ \(3\)」を追加すると \(4 + 1 + 3 = 8\)。これは \(10\) 以下なので、1段目に置けます。現在の幅 = \(8\)
3. 3冊目 (5cm): 1段目に「隙間 \(1\) + 厚さ \(5\)」を追加すると \(8 + 1 + 5 = 14\)。これは \(10\) を超えるため、2段目に移ります。現在の幅 = \(5\)
4. 4冊目 (2cm): 2段目に「隙間 \(1\) + 厚さ \(2\)」を追加すると \(5 + 1 + 2 = 8\)。これは \(10\) 以下なので、2段目に置けます。現在の幅 = \(8\)

結果、必要な段数は \(2\) 段となります。

アルゴリズム

以下の手順でプログラムを実装します。

1. 最初の本（\(L_1\)）を \(1\) 段目に配置し、rows（段数）を \(1\)、current_width（現在の段の合計幅）を \(L_1\) で初期化します。
2. \(2\) 冊目から \(N\) 冊目まで、順番に以下の処理を繰り返します。
   • もし current_width + 1 + L[i] <= W ならば：
     • 同じ段に置けるため、current_width に 1 + L[i] を加算します。
   • そうでなければ（はみ出す場合）：
     • 新しい段が必要なため、rows を \(1\) 増やします。
     • 新しい段の最初の本として配置するため、current_width を \(L[i]\) で更新します。
3. 最終的な rows の値を出力します。

計算量

• 時間計算量: \(O(N)\) \(N\) 冊の本を一度ずつ走査するため、本の冊数に比例した時間で計算が終わります。制約の \(N \leq 10^6\) に対しても十分に高速です。
• 空間計算量: \(O(N)\) すべての本の厚さをリストに格納する場合、入力サイズに比例したメモリを使用します。

実装のポイント

• 入力の高速化: \(N\) が最大 \(10^6\) と非常に大きいため、Python標準の input() を繰り返すよりも sys.stdin.read().split() を使って一括で入力を取得するほうが実行時間を短縮できます。

• 初期状態の扱い: 最初の \(1\) 冊目は必ず \(1\) 段目に入るため、ループの前に処理しておくと、ループ内での「隙間 \(1\)」の判定がシンプルになります。

  ソースコード

import sys

def solve():
    # 入力を一度に取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    W = int(input_data[1])
    L = list(map(int, input_data[2:]))
    
    if N == 0:
        print(0)
        return

    rows = 1
    current_width = L[0]
    
    for i in range(1, N):
        # 現在の段に隙間(1)と次の本(L[i])を追加した時の幅を計算
        if current_width + 1 + L[i] <= W:
            current_width += 1 + L[i]
        else:
            # はみ出す場合は新しい段へ
            rows += 1
            current_width = L[i]
            
    print(rows)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。