概要

靴下の色の濃さを並べ替えた上で、隣り合う靴下同士をペアにする／しないを選び、ちょうど \(M\) 組のペアの違和感（差の絶対値）の合計最小を求める問題です。

考察

1. まずソートするのが本質

色の濃さ \(S_i\) は大小関係しか効かないので、\(S\) を昇順にソートして $\(S_0 \le S_1 \le \dots \le S_{N-1}\)$ として考えます。以後、靴下はこの順番で扱います。

2. 最適解では「ペアはソート後に隣り合う2枚」でよい

直感的には、差の絶対値 \(|S_i-S_j|\) を小さくするには近い値同士を組ませるべきです。

実際、ソート後に \(i<j\) をペアにする場合、もし間にある \(S_{i+1}\) が未使用なら、\((i,j)\) を \((i,i+1)\) に変えると差は $\(S_{i+1}-S_i \le S_j-S_i\)$ となり悪化しません（むしろ改善します）。
また、間の要素が別のペアに入っている場合も、「交差するペアはほどいて近い同士に組み替える」操作で合計を増やさずに整理でき、最終的に「使うなら隣同士を組む」形にできます。

その結果、この問題は次の形に落とせます：

• ソート後の隣接差分 $\(w_i = S_{i+1}-S_i \quad (i=0,\dots,N-2)\)$ を考える。
• ペア \((S_i,S_{i+1})\) を作ることは、重み \(w_i\) の「辺」を選ぶことに対応する。
• 同じ靴下を2回使えないので、隣接する辺 \(w_i\) と \(w_{i+1}\) は同時に選べない（＝連続して選べない）。
• よって「長さ \(N-1\) の配列 \(w\) から、隣り合わない要素をちょうど \(M\) 個選んで和を最小化」になっている。

3. 素朴DPは \(O(NM)\) で間に合わない

「先頭から見て、ペアにする／しない」をDPすると $\(dp[i][j] = i\text{番目まで見て }j\text{組作る最小コスト}\)\( のようになり、遷移はできるものの計算量が \)O(NM)\( になります。 制約は \)N\le 2\times 10^5,\ M\le 10^5$ なので、これは到底実行できません。

4. 「ちょうど \(M\) 個」をペナルティで解く（Aliens trick / WQS二分探索）

「ちょうど \(M\) 個選ぶ」を直接扱う代わりに、選ぶたびに一定の罰金（ペナルティ）\(\lambda\) を加えた問題を考えます：

• 各選択にコスト \(w_i+\lambda\) を課す
• 「何個選んでもよい」最小化を解く

\(\lambda\) を大きくすると選ぶのが損になり個数が減り、\(\lambda\) を小さく（負に）すると個数が増えます。
この「最適解の個数が \(\lambda\) に対して単調に変化する」性質を使って二分探索で \(M\) 個付近に調整します。

アルゴリズム

1. 前処理

1. \(S\) をソート
2. \(w_i = S_{i+1}-S_i\)（長さ \(N-1\)）を作る

2. 固定した \(\lambda\) に対するDP（\(O(N)\)）

「\(w\) から隣り合わない要素を選ぶ」問題（最大独立集合的な形）なので、次の2状態DPで解けます。

• dp0: 直前の要素を選んでいない状態での最良（ペナルティ込みコスト, 選んだ個数）
• dp1: 直前の要素を選んだ状態での最良（ペナルティ込みコスト, 選んだ個数）

各 \(w\) を順に見て遷移します：

• 新しい dp0：前が選ばれていてもいなくても「今は選ばない」なので min(dp0, dp1)
• 新しい dp1：今を選ぶには前を選んでいない必要があるので dp0 + (w+\lambda)

このときコードでは - コストが小さい方を優先 - コストが同じなら「選んだ個数が多い方」を優先 という比較をしています。これは二分探索で「\(\lambda\) を上げたら個数が減る」という単調性を壊さないための重要な工夫です。

DPの返り値は： - その \(\lambda\) での最小（\(\sum w + \lambda \times \#選択\)） - そのとき選ばれた個数 cnt

3. \(\lambda\) を二分探索

cnt(λ) は \(\lambda\) を大きくするほど減る（単調減少）ので、

• cnt(λ) >= M を満たす最大の \(\lambda\) を二分探索で探す

コード中の範囲 - low = -1_000_000_010：十分負なのでたくさん選びやすく cnt >= M 側 - high = 1_000_000_010：十分正なのでほぼ選ばず cnt < M 側 として挟み撃ちしています。

4. 最終回答の復元

二分探索で得た \(\lambda\) についてDPすると、ペナルティ込みの最小値 cost が得られます（これは \(cost = C + \lambda \cdot cnt\) の形）。

求めたいのは「ちょうど \(M\) 個」の本来のコスト \(C\) なので、ペナルティ分を \(M\) 個分だけ戻して $\(\text{answer} = cost - \lambda \cdot M\)$ とします（コードの ans = cost - lam * M）。

計算量

• 時間計算量: ソートが \(O(N\log N)\)、DPが1回 \(O(N)\)、二分探索が約 \(O(\log 10^9)\approx 31\) 回なので
  $\(O(N\log N + N\log 10^9)\)$
• 空間計算量: 差分配列 \(w\) に \(O(N)\)、DP自体は定数個の変数のみなので
  $\(O(N)\)$

実装のポイント

• DPでの比較（同コストなら個数が多い方を採用）が非常に重要です。これがないと、\(\lambda\) の二分探索で cnt の単調性が崩れて不安定になります。

• 値は最大で \(10^9\)、\(N\) は \(2\times 10^5\) なので合計は \(10^{14}\) 規模になります。Pythonなら自動で多倍長ですが、INF は十分大きく（コードでは \(10^{30}\)）しておくのが安全です。

• 入力は大きいので sys.stdin.buffer.read() でまとめて読むのが高速です。

  ソースコード

import sys

def solve_lambda(weights, lam):
    INF = 10**30
    dp0_c, dp0_k = 0, 0          # previous item not taken
    dp1_c, dp1_k = INF, -10**18  # previous item taken

    for w in weights:
        a0_c, a0_k = dp0_c, dp0_k
        a1_c, a1_k = dp1_c, dp1_k

        # new dp0 = best of (a0, a1)
        if a0_c < a1_c or (a0_c == a1_c and a0_k > a1_k):
            ndp0_c, ndp0_k = a0_c, a0_k
        else:
            ndp0_c, ndp0_k = a1_c, a1_k

        # new dp1 = take current (must come from a0)
        ndp1_c = a0_c + w + lam
        ndp1_k = a0_k + 1

        dp0_c, dp0_k = ndp0_c, ndp0_k
        dp1_c, dp1_k = ndp1_c, ndp1_k

    # best at end
    if dp0_c < dp1_c or (dp0_c == dp1_c and dp0_k > dp1_k):
        return dp0_c, dp0_k
    else:
        return dp1_c, dp1_k

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    S = data[2:]
    S.sort()

    weights = [S[i + 1] - S[i] for i in range(N - 1)]

    low = -1_000_000_010  # always enough pairs
    high = 1_000_000_010  # always too few pairs (0)

    # binary search for maximum lambda with count >= M
    while high - low > 1:
        mid = (low + high) // 2
        _, cnt = solve_lambda(weights, mid)
        if cnt >= M:
            low = mid
        else:
            high = mid

    lam = low
    cost, cnt = solve_lambda(weights, lam)
    ans = cost - lam * M
    print(ans)

if __name__ == "__main__":
    main()

---

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