概要

\(N\) 個のりんごを \(K\) 個の箱に分けるとき、各箱の「最大重量 - 最小重量」の合計を最小化する問題です。ソート後に「どこで区切るか」を貪欲に選ぶことで効率的に解けます。

考察

重要な気づき1: ソートして連続区間に分ける

同じ箱に入れるりんごは、重さでソートしたときに連続した区間から選ぶのが最適です。

なぜなら、箱のばらつき度は「最大値 - 最小値」なので、飛び飛びの値を選ぶと無駄にばらつき度が大きくなってしまうからです。

例: 重さが \([1, 3, 5, 7]\) のりんごがあるとき - \(\{1, 7\}\) を同じ箱に入れる → ばらつき度 = \(7 - 1 = 6\) - \(\{1, 3\}\) を同じ箱に入れる → ばらつき度 = \(3 - 1 = 2\)

重要な気づき2: 分割問題として捉える

ソート済みの配列を \(K\) 個の連続区間に分割する問題と考えます。

全りんごを1つの箱に入れた場合のばらつき度は \(A[N-1] - A[0]\) です。

ここで、隣接要素間の差（ギャップ）\(gap[i] = A[i+1] - A[i]\) に注目します。

\(K\) 個の箱に分けるには \(K-1\) 箇所で分割します。位置 \(i\) で分割すると、その \(gap[i]\) の分だけばらつき度の合計が減ります。

具体例

\(A = [1, 2, 5, 8, 9]\)、\(K = 3\) の場合：

• ギャップ: \([1, 3, 3, 1]\)（それぞれ \(2-1, 5-2, 8-5, 9-8\)）
• 1箱の場合のばらつき度: \(9 - 1 = 8\)
• \(K-1 = 2\) 箇所で切る → 最大のギャップ \(3, 3\) で切る
• 結果: \([1, 2], [5], [8, 9]\) に分割
• ばらつき度の合計: \((2-1) + 0 + (9-8) = 1 + 0 + 1 = 2\)
• 計算: \(8 - 3 - 3 = 2\) ✓

素朴なDPアプローチ

\(dp[i][j]\) = 最初の \(i\) 個を \(j\) 箱に分けたときの最小ばらつき度、とするDPは \(O(N^2 K)\) となり、\(N = 2 \times 10^5\) では TLE します。

アルゴリズム

1. りんごの重さをソートする
2. \(K \geq N\) なら、各りんごを別の箱に入れられるので答えは \(0\)
3. 隣接要素間のギャップ \(gap[i] = A[i+1] - A[i]\) を全て計算
4. 1箱の場合のばらつき度 \(total = A[N-1] - A[0]\) を求める
5. ギャップを降順ソートし、上位 \(K-1\) 個のギャップを \(total\) から引く
6. 結果を出力

直感的な理解: 大きなギャップで切ることで、ばらつき度を効率的に減らせます。

計算量

• 時間計算量: \(O(N \log N)\)（ソートがボトルネック）
• 空間計算量: \(O(N)\)（配列の保持）

実装のポイント

• \(K \geq N\) の場合は特別に処理（答えは \(0\)）

• ギャップの配列サイズは \(N-1\) 個であることに注意

• ギャップを降順ソートして上位 \(K-1\) 個を選ぶ（または昇順ソートして下位を残す）

  ソースコード

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # ソートする（同じ箱には連続した重さのりんごを入れるのが最適）
    A.sort()
    
    # dp[i][j] = 最初のi個のりんごをj個の箱に分けたときのばらつき度の合計の最小値
    # これだとO(N^2 * K)になり、TLEする可能性が高い
    
    # 別のアプローチ：
    # ソート後、N個のりんごをK個の連続区間に分ける
    # 各区間[l, r]のばらつき度は A[r] - A[l]
    # 全体のばらつき度の合計 = sum(A[r_i] - A[l_i]) for each box i
    # 
    # 全てのりんごを1つの箱に入れた場合: A[N-1] - A[0]
    # K個の箱に分けるとは、K-1箇所で分割すること
    # 分割位置iとi+1の間で切ると、A[i+1] - A[i]だけばらつき度が減る（隣接する箱の境界で）
    #
    # より正確には：
    # 全体を通して見ると、ばらつき度の合計は
    # (各箱の最大値の合計) - (各箱の最小値の合計)
    # 
    # K-1箇所の分割点を選ぶと考える
    # 分割点をi (0 <= i < N-1)とすると、iとi+1の間で切る
    # 
    # 1つの箱の場合: A[N-1] - A[0]
    # 分割点iで切ると、その分割によって減少する量は
    # 切る前: ...A[i], A[i+1]... が同じ箱
    # 切った後: ...A[i] | A[i+1]...
    # 
    # 実際には、隣接要素の差 gap[i] = A[i+1] - A[i] を考え、
    # K-1個の最大のgapで切るのが最適
    
    if K >= N:
        # 各りんごを別々の箱に入れられる（余る箱があってもOK）
        print(0)
        return
    
    # 隣接要素間の差を計算
    gaps = []
    for i in range(N - 1):
        gaps.append(A[i + 1] - A[i])
    
    # 全体のばらつき度（1つの箱に全部入れた場合）
    total = A[N - 1] - A[0]
    
    # K-1個の分割点を選ぶ = K-1個の最大のgapで切る
    # 切った箇所のgapは、ばらつき度の計算から除外される
    gaps.sort(reverse=True)
    
    # K-1個の最大のgapを引く
    for i in range(K - 1):
        total -= gaps[i]
    
    print(total)

solve()

---

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