概要

りんごの重さを並べ替えてから「箱の切れ目」を作る問題に言い換え、隣り合う重さの差（ギャップ）が大きいところで切るほど、ばらつき度の合計を小さくできます。

考察

重要な気づき 1：最適な分け方は「ソート後に連続な区間」にできる

重さを昇順に並べた列を考えます。ある箱に入るりんごがソート順で飛び飛び（例：小さいのと大きいのを同じ箱に入れ、中間が別箱）だと、その箱の最大値−最小値が無駄に大きくなりがちです。

実際、ソート後に - 箱Xに \(A_i\) と \(A_k\)（\(i<k\)） - 箱Yにその間の \(A_j\)（\(i<j<k\)） のような状況があると、箱Xの範囲は少なくとも \(A_k-A_i\) ですが、\(A_j\) を箱Xに寄せる／箱Xの端の要素を箱Yに寄せるなどの調整で、各箱の範囲（最大−最小）を悪化させずに「連続区間の箱詰め」に直せます。
よって、ソートした配列を \(K\) 個の連続区間に切る問題として考えてよいです。

重要な気づき 2：切れ目を入れると「ギャップ分だけ」合計が減る

ソート済み配列 \(A\) を 1つの箱に全部入れると、ばらつき度は \(A_{N}-A_{1}\)（ここでは1-index風に書きます）です。

ここで、例えば \(A_t\) と \(A_{t+1}\) の間で箱を分ける（切れ目を入れる）と、 - 左の箱の範囲：\(A_t - A_1\) - 右の箱の範囲：\(A_N - A_{t+1}\)

合計は
$\((A_t-A_1) + (A_N-A_{t+1}) = (A_N-A_1) - (A_{t+1}-A_t)\)$

つまり、切れ目を入れると、その場所のギャップ \((A_{t+1}-A_t)\) だけ合計が減ることが分かります。

したがって、\(K\) 箱にするには切れ目が \(K-1\) 個必要なので、合計を最小にするには - 減らせる量（ギャップ）の合計を最大化する - つまり 隣接差の大きい場所を \(K-1\) 個選んで切る のが最適です。

素朴なアプローチが難しい理由

「どこで切るか」を全探索すると、切れ目の選び方は組合せ的に増え（例：\(N\) が \(2\times 10^5\) なので論外）、DPもそのままだと \(O(NK)\) になり得て間に合いません。
上の観察により、最大のギャップを選ぶだけに落とせるため高速化できます。

アルゴリズム

1. 配列 \(A\) を昇順にソートする。
2. 隣接差（ギャップ）\(g_i = A_{i+1}-A_i\)（\(i=1..N-1\)）を作る。
3. ギャップを大きい順にソートし、上位 \(K-1\) 個の和を removed とする。
4. 全体を1箱に入れたときの範囲は \((A_N - A_1)\) なので、答えは
   $\(\text{ans} = (A_N - A_1) - \sum_{i=1}^{K-1} (\text{大きいギャップ}_i)\)$
5. 例外：
   • \(K=N\)（各箱1個）なら答えは \(0\)
   • \(K=1\) なら答えは \(A_N-A_1\)

具体例

\(A=[1, 3, 6, 10],\ K=2\)
ギャップは \([2,3,4]\)。最大の \(K-1=1\) 個は \(4\)。
全体範囲 \(10-1=9\) なので、答えは \(9-4=5\)。
実際、\([1,3,6]\) と \([10]\) に分けると、ばらつき度は \((6-1)+0=5\) で最小です。

計算量

• 時間計算量: \(O(N\log N)\)（ソートが支配的：\(A\) のソートとギャップのソート）
• 空間計算量: \(O(N)\)（ギャップ配列）

実装のポイント

• \(K=N\) のときは必ず \(0\) になるので早期リターンすると安全です。

• Pythonではソートが高速なので、ギャップを降順ソートして先頭 \(K-1\) 個を足す実装が簡潔です。

• 値は最大で \(10^9\)、差や合計は \(2\times 10^5\) 個分足す可能性があるため、Pythonの整数（任意精度）ならそのままで問題ありません。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    if N == 1 or K == N:
        print(0)
        return
    if K == 1:
        print(A[-1] - A[0])
        return

    gaps = [A[i+1] - A[i] for i in range(N - 1)]
    gaps.sort(reverse=True)
    removed = sum(gaps[:K-1])
    ans = (A[-1] - A[0]) - removed
    print(ans)

if __name__ == "__main__":
    main()

---

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