概要

本棚にブックエンドと \(N\) 冊の本を並べたときの、左端から右端までの最小距離を求める問題です。本の並べ方によらず答えは一定であることに気づくのがポイントです。

考察

まず、本棚の配置を左から順に図示してみましょう。

|<-- S -->|<- K ->|<- D_a ->|<- K ->|<- D_b ->|<- K ->| ... |<- K ->|<- D_? ->|
ブックエンド   間隔    本1      間隔    本2      間隔          間隔    本N

重要な気づき：本をどの順番で並べても、全体の距離は変わらない。

その理由を考えてみます。全体の距離は次のように分解できます。

1. ブックエンドの幅: \(S\)（固定）
2. 間隔の合計: ブックエンドと最初の本の間に \(K\)、その後 \(N-1\) 箇所の本同士の間にそれぞれ \(K\)。合計 \(N \times K\)
3. 本の厚さの合計: \(D_1 + D_2 + \cdots + D_N\)（順番を変えても合計は同じ）

間隔は「少なくとも \(K\)」ですが、全体の距離を最小化したいので、各間隔をちょうど \(K\)（最小値）にするのが最適です。

また、本の並べ順を変えても、足し算の順番が変わるだけで合計値には影響しません。例えば \(N = 3\), \(S = 2\), \(K = 1\), \(D = [3, 5, 7]\) の場合：

\[\text{合計} = S + N \times K + \sum_{i=1}^{N} D_i = 2 + 3 \times 1 + (3 + 5 + 7) = 2 + 3 + 15 = 20\]

どの順番で本を並べても答えは \(20\) です。

アルゴリズム

以上の考察から、以下の単純な式で答えが求まります。

\[\text{答え} = S + N \times K + \sum_{i=1}^{N} D_i\]

手順： 1. \(N\), \(S\), \(K\) と各本の厚さ \(D_i\) を読み込む 2. 上記の式を計算して出力する

計算量

• 時間計算量: \(O(N)\)（\(D_i\) の総和を計算するため）
• 空間計算量: \(O(N)\)（配列 \(D\) の格納）

実装のポイント

• \(N\), \(S\), \(K\), \(D_i\) がそれぞれ最大 \(10^9\) なので、答えは最大で約 \(10^9 + 10^5 \times 10^9 + 10^5 \times 10^9 \approx 2 \times 10^{14}\) 程度になります。C++ などでは long long を使う必要がありますが、Python では整数のオーバーフローを気にする必要はありません。

• 「少なくとも \(K\) の間隔」という条件は、最小化問題なのでちょうど \(K\) にすればよい、と読み替えるのがポイントです。

  ソースコード

N, S, K = map(int, input().split())
D = list(map(int, input().split()))

# The layout from left to right:
# [Bookend: width S] [gap >= K] [Book1] [gap >= K] [Book2] ... [gap >= K] [BookN]
# Total distance = S + N * K + sum(D)
# The order of books doesn't matter since all gaps are exactly K and all books must be placed.

total = S + N * K + sum(D)
print(total)

この解説は claude4.6opus-thinking によって生成されました。