概要

本を好きな順に並べられるとき、必要な間隔をすべて最小の \(K\) に詰めた場合の全長を数え上げれば、最小距離がそのまま求まる問題です。

考察

まず、求めたい距離は「ブックエンドの左端」から「一番右の本の右端」までの長さです。

並べ方（本の順番）は自由ですが、どの順番でも本の厚さの合計 \(\sum D_i\) は変わりません。また、規則で必要な「間隔」は以下の通りです。

• ブックエンドと最左の本の間に少なくとも \(K\)
• 隣り合う本どうしの間に少なくとも \(K\)（本が \(N\) 冊なら隣接は \(N-1\) 箇所）

最小にしたいので、これらの間隔はすべて ちょうど \(K\) にするのが最適です（それ以上広げると距離が増えるだけ）。

ここで間隔の個数に注意します：

• ブックエンド〜1冊目：\(1\) 個
• 本〜本：\(N-1\) 個

合計で \(1 + (N-1) = N\) 個の間隔が必要なので、間隔分の長さは \(N \cdot K\) です。

よって、最小距離は [ S + \sum_{i=1}^{N} D_i + N\cdot K ] となり、本の順番を工夫する必要はありません。

（例）\(N=3, S=10, K=2, D=[4,1,7]\) のとき
厚さ合計 \(=12\)、間隔は \(3\) 個なので \(3\cdot2=6\)。
答えは \(10+12+6=28\)。

素朴に「最適な並べ替え」を探索（全探索）すると \(N!\) 通りで到底間に合いませんが、上の観察により並べ替え自体が不要になります。

アルゴリズム

1. 入力から \(N,S,K\) を読む
2. 厚さの合計 \(T=\sum D_i\) を計算する
3. 答えを \(S + T + N\cdot K\) として出力する

計算量

• 時間計算量: \(O(N)\)（厚さを合計するだけ）
• 空間計算量: \(O(1)\)（合計値など定数個のみ。入力配列を保持しない実装なら定数）

実装のポイント

• \(S, K, D_i\) は最大 \(10^9\)、\(N\) は最大 \(10^5\) なので、答えは最大でおよそ \(10^{14}\) になります。64bit 整数が必要ですが、Python の int なら安全です。

• 間隔の数は \(N-1\) ではなく \(N\)（ブックエンドとの間の \(1\) 個を忘れない）点が典型的な注意点です。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.read().strip().split())
    N = int(next(it))
    S = int(next(it))
    K = int(next(it))
    total_thickness = sum(int(next(it)) for _ in range(N))
    ans = S + total_thickness + N * K
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。