概要

本を並べる順番を工夫することで、本棚の必要な長さを最小化する問題です。本の厚さと必要な間隔、ブックエンドの幅が与えられたときに、全体の最小の長さを求めます。

考察

まず、問題の条件を整理しましょう。

• 本は一列に並べる。
• 隣接する本同士の間、および最も左の本とブックエンドの間には、最低 \(K\) センチメートルの隙間が必要。
• ブックエンドの幅は \(S\) センチメートルあり、その左端が本棚の始点。
• 本の厚さは配列 \(D\) で与えられ、並び順は自由。

直感的に考えると、本をどのように並べるかで全体の長さが変わる気がしますが、実は本の順序にかかわらず、全体の長さは一定になります。

なぜ順序に依存しないのか？

本棚の長さは次のように構成されます：

1. ブックエンドの左端から最初の本の左端までの距離：これは最低でも \(K\) 必要なので、最初の本の左端は位置 \(S + K\) に配置するのが最適。
2. すべての本の厚さの合計：\(\sum_{i=1}^{N} D_i\)。これは並び順に関係なく一定。
3. 本と本の間の間隔の合計：\(N - 1\) 箇所あり、それぞれ最低 \(K\) 必要。よって合計 \((N - 1) \times K\)。

したがって、全体の長さは：

\[ \text{長さ} = (S + K) + \sum D_i + (N - 1) \times K = S + \sum D_i + N \times K \]

となり、本の並び順には一切依存しません。

したがって、答えは単純にこの式を計算するだけで求められます。

アルゴリズム

1. すべての本の厚さの合計 \(\sum D_i\) を計算。
2. 式 \(S + \sum D_i + N \times K\) を計算して出力。

計算量

• 時間計算量: \(O(N)\)（合計を取るだけ）
• 空間計算量: \(O(1)\)（入力を除けば定数メモリ）

実装のポイント

• 本の並び替えは不要。
• 合計を高速に求めること（Pythonなら sum() で十分）。
• オーバーフローに注意（Pythonでは問題なし）。

## ソースコード

```python
import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    S = int(data[1])
    K = int(data[2])
    D = list(map(int, data[3:]))

    # 本の厚さを昇順にソート
    D.sort()

    # 累積和を計算（間隔を考慮しない本の厚さの合計）
    # 先頭に0を追加して、累積和のインデックス操作を簡単にする
    acc = [0] + list(accumulate(D))
    
    min_length = float('inf')
    
    # 最も左の本と最も右の本の間にある本の数をiとして全探索
    # i は 0 から N-1 まで
    for i in range(N):
        # 左端の本と右端の本の間にある i 冊の本を選ぶ（厚さが最小の i 冊）
        # 左端の本: 厚さ最大の本
        # 右端の本: 厚さ最大の本（ただし既に選ばれていないもの）
        # 実際には、両端に厚い本を持ってきて、間に薄い本を並べるのが最適
        
        # 実際に最適な配置は：
        # 両端に厚い本を持ってきて、間に薄い本を挟む
        # つまり、最大2冊の厚い本を両端に置き、残りのN-2冊を間に置くのが良いか？
        # でも、N=1 の場合もあるので注意
        
        # よりシンプルな方法：
        # 本をソートしておいて、連続する部分列を選び、両端に厚い本を配置するイメージ
        # しかし、実は最適なのは、両端に最も厚い本を置き、間に残りを置くことではないかもしれない
        
        # 正しいアプローチ：
        # 総和 = 本の厚さの合計 + 間隔の合計
        # 間隔の数 = 本の数 (N) → N+1個の物体（ブックエンド含む）の間の数 = N
        # いや、問題文をよく読むと：
        
        """
        - ブックエンドの左端から最初の本の左端までは >= K
        - 各本の間も >= K
        - 最後の本の右端からそれ以上先は関係ない
        - よって、距離 = (最初の本の左端 - ブックエンドの左端) + すべての本の厚さ + (各本の間の間隔)
          つまり:
          distance = K + sum(D) + (N-1)*K = sum(D) + N*K
          これは本の順番に依らない！？
          
          いや、待て。ブックエンドの幅Sがある。
          ブックエンドの左端から最初の本の左端が >= K なら、
          最初の本の左端はブックエンドの右端以降でもよい。
          つまり、最初の本の左端 >= S + K とする必要がある。
          そして、ブックエンドの左端から最初の本の左端がちょうどKであれば、それが最小。
          よって、最初の本の左端 = S + K
          そこから右に本を並べていく。
          
          距離 = (最初の本の左端 - ブックエンドの左端) + (すべての本の厚さ) + (本の間の間隔)
               = (S + K) + sum(D) + (N-1)*K
               = S + K + sum(D) + (N-1)*K
               = S + sum(D) + N*K
        """
        
        # 上記のように思えるが、問題は本を好きな順番で並べられること。
        # しかし、上記の式は本の順序によらず一定である。
        # よって、答えは常に S + sum(D) + N * K
        
        # と思ったが、よく見ると、
        # 「最も左の本はブックエンドとの間にもKセンチ以上必要」
        # これは、「ブックエンドの右端」からの距離ではなく、
        # 「ブックエンドの左端」からの距離がK以上必要ということか？
        # それとも、「ブックエンドの右端」からの距離がK以上必要？
        
        # 問題文再確認：
        # 「本棚の左端にはブックエンド（幅 S ）が固定されており、
        # 最も左の本はブックエンドとの間にも K センチメートル以上の間隔が必要です。」
        # つまり、ブックエンドの右端から本の左端までが K 以上必要。
        
        # よって、最初の本の左端は位置 S + K に配置される。
        # 次の本は、一つ前の本の右端から K センチ空けて配置。
        # よって、全体の長さは:
        # 最初の本の左端の位置: S + K
        # すべての本の厚さの合計: sum(D)
        # 本の間の間隔の合計: (N - 1) * K
        # よって、最後の本の右端の位置は:
        # (S + K) + sum(D) + (N - 1) * K = S + sum(D) + N * K
        
        # 従って、答えは常に S + sum(D) + N * K
        # しかし、これは本の順序に依らないので、最小値もこの値そのもの。
        
        # と思ったが、勘違いしていた。
        # 実際には、本を並べる「順番」によって、最後の本の右端の位置が変わる可能性があるか？
        # 例えば、厚い本を最初に置くと、その後の本が遠くに行ってしまう？
        # いや、それは関係ない。結局全部並べる必要があるので、総和は同じ。
        
        # よって、答えは一意に決まる。
        
    total_thickness = sum(D)
    result = S + total_thickness + N * K
    print(result)

if __name__ == "__main__":
    main()

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