概要

\(N\) 冊の本とブックエンドを、決められた最小間隔 \(K\) 以上を空けて一列に並べるとき、全体の端から端までの長さの最小値を求める問題です。

考察

一見すると「どのような順番で本を並べるべきか」を考える必要があるように見えますが、実は本の並び順は答えに影響しません。全体の長さを構成する要素を分解して考えてみましょう。

全体の長さは、以下の 3 つの要素の合計となります。

1. ブックエンドの幅: \(S\) センチメートル（固定）
2. 本の間隔（隙間）の合計:
   • ブックエンドと 1 冊目の本の間に \(K\) センチメートル以上の隙間が必要です（1 箇所）。
   • 隣り合う本同士（\(N\) 冊の本の間）に、それぞれ \(K\) センチメートル以上の隙間が必要です（\(N-1\) 箇所）。
   • よって、隙間は合計で \(1 + (N-1) = N\) 箇所必要になります。全体の長さを最小にするには、これらすべての隙間を最小値である \(K\) センチメートルにすればよいです。
3. すべての本の厚さの合計:
   • 各本の厚さを \(D_1, D_2, \ldots, D_N\) とすると、その合計は \(\sum_{i=1}^{N} D_i\) となります。本をどのような順番で並べても、この総和は変わりません。

これらをすべて足し合わせると、求める最小値は以下の式で表せます。 $\(\text{最小距離} = S + (N \times K) + \sum_{i=1}^{N} D_i\)$

アルゴリズム

1. 入力から \(N, S, K\) および各本の厚さ \(D_i\) を読み込みます。
2. \(N\) 冊の本の厚さの総和 \(D_{sum}\) を計算します。
3. 公式 \(S + (N \times K) + D_{sum}\) に当てはめて計算します。
4. 計算結果を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 本の厚さの総和を計算するために、入力された \(N\) 個のデータを 1 回走査する必要があります。
• 空間計算量: \(O(N)\)
  • 入力されたすべての本の厚さをリスト等に保持する場合、\(O(N)\) のメモリを使用します。

実装のポイント

• \(N\) や \(D_i\) の値が大きいため、合計値が 32 ビット整数の範囲を超える可能性があります。Python では自動的に多倍長整数として扱われるため問題ありませんが、他の言語（C++ など）を使用する場合は 64 ビット整数型（long long など）を使用するように注意してください。

• 隙間の数が \(N-1\) ではなく、ブックエンドとの間を含めて \(N\) になる点に注意しましょう。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白（スペース、改行など）で分割します
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
        
    # 各値を取得
    # N: 本の冊数
    # S: ブックエンドの幅
    # K: 必要な最小間隔
    n = int(input_data[0])
    s = int(input_data[1])
    k = int(input_data[2])
    
    # 各本の厚さ D_i の総和を計算
    # 本を並べる順番に関わらず、厚さの合計と隙間の合計は一定です
    d_sum = sum(map(int, input_data[3:3+n]))
    
    # 最小距離を計算
    # 距離 = ブックエンドの幅 + (N 個の隙間 × K) + 全ての本の厚さの合計
    # - ブックエンドと1冊目の本の間に隙間 K が必要
    # - 隣り合う本同士の間 (N-1 箇所) にそれぞれ隙間 K が必要
    # 合計で N 箇所の隙間が必要となります
    ans = s + (n * k) + d_sum
    
    # 結果を出力
    print(ans)

if __name__ == '__main__':
    main()

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