概要

本を並べ替えて隣り合う本の厚さの差の絶対値の総和を最小化する問題です。ソートして並べると、答えは最大値と最小値の差になります。

考察

重要な気づき

まず、具体例で考えてみましょう。厚さが \([3, 1, 4, 1, 5]\) の本があるとします。

これをソートすると \([1, 1, 3, 4, 5]\) となります。このとき隣り合う差の総和は： $\(|1-1| + |3-1| + |4-3| + |5-4| = 0 + 2 + 1 + 1 = 4\)$

これは実は \(5 - 1 = 4\)（最大値 - 最小値）と一致しています。

なぜソートが最適なのか

ソートして並べた場合、各本の厚さは単調増加（または同じ）になります。このとき： $\(\sum_{i=1}^{N-1} |V_{i+1} - V_i| = \sum_{i=1}^{N-1} (V_{i+1} - V_i) = V_N - V_1\)$

つまり、差の総和は「最大値 - 最小値」に等しくなります。

なぜこれが最小なのか

どんな並べ方をしても、「最大値 - 最小値」より小さくすることはできません。

理由：最小の本から最大の本まで、どのような経路で並べても、その「道のり」は少なくとも「直線距離」（最大値 - 最小値）以上になります。ソートして並べると、無駄な往復がなくなり、ちょうど「直線距離」だけで済みます。

逆に、ソートしない並べ方では値が増減を繰り返し、同じ区間を何度も通ることになり、総和が大きくなってしまいます。

素朴なアプローチ

全ての並べ方を試すと \(N!\) 通りあり、\(N = 20\) 程度でもTLEになります。しかし、上記の考察から、ソートするだけで答えが求まることが分かります。

アルゴリズム

1. 本の厚さをソートする
2. ソート後の最大値（最後の要素）から最小値（最初の要素）を引いた値を出力する

n = int(input())
v = list(map(int, input().split()))
v.sort()
print(v[-1] - v[0])

計算量

• 時間計算量: \(O(N \log N)\)（ソートにかかる時間）
• 空間計算量: \(O(N)\)（配列の保持に必要）

実装のポイント

• ソート後、v[-1] で最大値、v[0] で最小値を取得できます

• \(N = 1\) の場合も正しく動作します（\(v[0] - v[0] = 0\) となる）

• Python の sort() は Timsort を使用しており、安定ソートで効率的です

  ソースコード

n = int(input())
v = list(map(int, input().split()))
v.sort()
print(v[-1] - v[0])

---

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