概要

\(N\) 冊の本を自由に並べ替え、隣り合う本の厚さの差の絶対値の総和を最小化する問題です。

考察

この問題のポイントは、「どのような順番で並べると差の合計が最も小さくなるか」を見極めることです。

直感的な観察

例えば、厚さが \(10, 30, 20\) の 3 冊の本がある場合を考えてみましょう。 - \([10, 30, 20]\) と並べた場合：\(|30 - 10| + |20 - 30| = 20 + 10 = 30\) - \([10, 20, 30]\) と並べた場合：\(|20 - 10| + |30 - 20| = 10 + 10 = 20\)

このように、値を小さい順（または大きい順）に並べたほうが、差の合計が小さくなりそうだと分かります。

数学的な裏付け

本を厚さの昇順に並べ替えたものを \(A_1, A_2, \dots, A_N\) とします（\(A_1 \leq A_2 \leq \dots \leq A_N\)）。 このとき、隣り合う差の絶対値の総和は以下のようになります。 \(|A_2 - A_1| + |A_3 - A_2| + \dots + |A_N - A_{N-1}|\)

すべての項が正（または \(0\)）なので、絶対値記号をそのまま外すことができます。 \((A_2 - A_1) + (A_3 - A_2) + \dots + (A_N - A_{N-1})\)

これを計算すると、途中の項がすべて打ち消し合い、最終的に残るのは \(A_N - A_1\)、つまり (最大値) - (最小値) だけになります。

どのような並べ方をしたとしても、最小の値から最大の値まで「移動」する必要があるため、総和が \(A_N - A_1\) を下回ることはありません。したがって、昇順（または降順）に並べたときが最小となります。

アルゴリズム

1. 入力された \(N\) 個の厚さ \(V_i\) の中から、最大値 \(V_{max}\) と最小値 \(V_{min}\) を見つけます。
2. \(V_{max} - V_{min}\) を計算して出力します。
3. ただし、\(N=1\) のときは隣り合う本が存在しないため、答えは \(0\) となります。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の要素を一度走査して最大値と最小値を求めるため、要素数に比例した時間で処理できます。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の値をリストに格納するために必要なメモリ量です。

実装のポイント

• \(N\) が最大 \(2 \times 10^5\) と比較的大きいため、Python の場合は sys.stdin.read().split() を使うなど、高速な入出力方法を利用すると安全です。

• 答えは非常に大きな値（最大 \(10^9\) 程度）になる可能性がありますが、Python の整数型は自動的に多倍長整数として扱われるため、オーバーフローの心配はありません。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにします。
    # これにより、大量の入力データ（N=2*10^5）を高速に処理できます。
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は何もせず終了します。
    if not input_data:
        return
    
    # 最初の要素は本の冊数 N です。
    n = int(input_data[0])
    
    # 本が1冊以下の場合は、隣り合う本が存在しないため、差の総和は 0 になります。
    if n < 2:
        print(0)
        return
    
    # 2番目以降の要素は各本の厚さ V_i です。
    # これらを整数のリストに変換します。
    v_values = list(map(int, input_data[1:]))
    
    # 隣り合う要素の差の絶対値の総和を最小にするには、
    # 本を厚さの昇順（または降順）に並べるのが最適です。
    # その場合、総和は (最大値 - 最小値) となります。
    # どのような並べ方でも、最小値から最大値までの移動は必ず含まれるため、
    # 総和が (最大値 - 最小値) を下回ることはありません。
    
    result = max(v_values) - min(v_values)
    
    # 結果を出力します。
    print(result)

if __name__ == "__main__":
    main()

---

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