概要

本棚の段に本を隙間を空けながら左から順に配置し、必要な段数を求める問題です。各段の横幅を超えないように本を配置していきます。

考察

問題のルールに従ってシミュレーションを行うことで解くことができます。重要な点は、現在の段に本が既にある場合、次の本を配置する際には1センチの隙間が必要になることです。素朴なアプローチでは、各本について現在の段の幅を確認しながら段を管理するだけで十分です。制約が \(N \leq 10^6\) と大きいですが、1回のループで処理できるため効率的です。

アルゴリズム

1. 現在の段の幅 current_width と段数 stages を初期化します（最初は1段から始まります）。
2. 各本について順番に処理します：
   • 現在の段に本が1冊もない場合（current_width == 0）、その本を現在の段の左端に配置し、current_width をその本の厚さに設定します。
   • 現在の段に本がある場合、現在の段の幅に1センチの隙間と次の本の厚さを足した値が段の横幅 \(W\) 以下かどうかをチェックします。
     • 超えない場合：現在の段の幅を更新し（current_width + 1 + L[i]）、同じ段に配置します。
     • 超える場合：新しい段に移り（stages を1増やし）、現在の段の幅を新しい本の厚さにリセットします。
3. すべての本を配置し終えた後、段数 stages を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 本の冊数 \(N\) に対して1回のループで処理するため。
• 空間計算量: \(O(N)\)
  • 本の厚さを格納するリストのサイズが \(N\) であるため。

実装のポイント

• 現在の段の幅が0かどうかで最初の本かどうかを判断します。

• 隙間を考慮するため、2冊目以降の本を配置する際は current_width + 1 + L[i] で判定します。

• 入力値が大きい場合でも効率的に処理できるように、シンプルなループで実装しています。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    W = int(data[1])
    L = list(map(int, data[2:2+n]))
    
    current_width = 0
    stages = 1
    
    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:
                stages += 1
                current_width = L[i]
                
    print(stages)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。