概要

\(N\) 個のりんごを \(K\) 個のグループ（箱）に分け、各グループの「最大値と最小値の差」の合計を最小化する問題です。

考察

1. りんごをソートして考える

直感的に、重さが近いりんご同士を同じ箱に入れたほうが「ばらつき度」は小さくなりそうです。 実際、りんごを重さの昇順に並べたとき、各箱にはソート後の配列で連続する範囲のりんごを入れるのが最適となります。

もし連続していない（間を飛ばして入れる）場合、その飛ばしたりんごをどちらかの箱に含めることで、ばらつき度を増やさずに箱をまとめることができるからです。

2. 数式で整理する

りんごをソートした結果を \(A'_1, A'_2, \ldots, A'_N\) とします。 これを \(K\) 個の連続する区間に分けるとします。例えば、1つ目の箱の範囲が \(A'_1\) から \(A'_{i_1}\)、2つ目の箱が \(A'_{i_1+1}\) から \(A'_{i_2}\) … といった具合です。

このとき、全箱のばらつき度の合計は以下のようになります： \((A'_{i_1} - A'_1) + (A'_{i_2} - A'_{i_1+1}) + \dots + (A'_N - A'_{i_{K-1}+1})\)

この式を少し変形してみましょう。 隣り合う要素の差を \(D_i = A'_{i+1} - A'_i\) と置くと、全体の範囲（最大値と最小値の差）は \(\sum_{i=1}^{N-1} D_i = A'_N - A'_1\) です。 上記の合計式は、「全体の差の合計」から「箱の境界線となる箇所の差」を引いたものとみなせます。

3. 最適な境界線の選び方

\(N\) 個の要素を \(K\) 個の区間に分けるには、隣り合う要素の間の隙間（全部で \(N-1\) 箇所）から \(K-1\) 箇所の「境界線」を選ぶことになります。

合計値を最小化するには、値の大きい隙間を \(K-1\) 個選んで境界線とし、それらを除外するのが最善です。 言い換えれば、値の小さい隙間を \(N-K\) 個選んで足し合わせることで、最小のばらつき度を求めることができます。

アルゴリズム

1. りんごの重さ \(A\) を昇順にソートする。
2. 隣り合う要素の差 \(D_i = A_{i+1} - A_i\) をすべて計算し、配列 \(D\) を作る（要素数は \(N-1\) 個）。
3. 差の配列 \(D\) を昇順にソートする。
4. \(D\) のうち、小さい方から \(N-K\) 個の和を計算して出力する。
   • \(K=1\) のときはすべての差を足す（\(A_N - A_1\) と等しい）。
   • \(K=N\) のときは何も足さない（結果は \(0\)）。

計算量

• 時間計算量: \(O(N \log N)\)
  • りんごの重さのソートに \(O(N \log N)\) かかります。
  • 差の計算に \(O(N)\)、差の配列のソートに \(O(N \log N)\) かかります。
• 空間計算量: \(O(N)\)
  • 入力データおよび差の配列を保持するために \(O(N)\) のメモリが必要です。

実装のポイント

• \(K=1\) や \(K=N\) のような端のケースでも、このアルゴリズム（小さい方から \(N-K\) 個選ぶ）は正しく動作します。

• \(N\) や \(A_i\) の値が大きいため、Pythonでは sys.stdin.read().split() を用いて一括で入力を読み込むと高速です。

  ソースコード

import sys

def solve():
    # Read all input data at once for efficient processing
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    a = list(map(int, input_data[2:]))
    
    # If the number of boxes is at least the number of apples,
    # each box can contain a single apple, resulting in a variability of 0.
    if k >= n:
        print(0)
        return
    
    # Sorting the apple weights allows us to group them into contiguous segments.
    # The sum of variabilities for K boxes is equivalent to the total range
    # (max(A) - min(A)) minus the (K-1) largest gaps between adjacent elements.
    a.sort()
    
    # Calculate the differences between adjacent apples in the sorted list.
    diffs = [a[i+1] - a[i] for i in range(n - 1)]
    
    # Sorting the differences to easily pick the smallest or largest ones.
    diffs.sort()
    
    # To minimize the sum of variabilities, we keep the (n-k) smallest differences
    # within the boxes and treat the (k-1) largest differences as boundaries between boxes.
    print(sum(diffs[:n-k]))

if __name__ == '__main__':
    solve()

---

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