概要

\(N\) 枚の靴下から \(M\) 組のペアを作り、各ペアの色の濃さの差の絶対値の合計を最小化する問題。ソート後に隣接差分配列から「隣接しない \(M\) 個の要素を選んで和を最小化する」問題に帰着し、後悔付き貪欲法で効率的に解く。

考察

観察1: ソートすると最適ペアは隣接要素になる

靴下を色の濃さ \(S\) でソートすると、最適なペアリングでは必ずソート後に隣接する靴下同士がペアになります。直感的には、\(a \leq b \leq c\) のとき \(|c - a| \geq |b - a|\) かつ \(|c - a| \geq |c - b|\) なので、離れた要素をペアにするよりも近い要素をペアにする方が得です。

観察2: 差分配列の問題に帰着

ソート後の差分 \(d[i] = S[i+1] - S[i]\)（\(i = 0, 1, \ldots, N-2\)）を定義します。靴下 \(i\) と靴下 \(i+1\) をペアにすると、コストは \(d[i]\) です。

ここで重要な制約は、靴下は一度しか使えないことです。例えば \((S[0], S[1])\) をペアにしたら、\(S[1]\) は使用済みなので \((S[1], S[2])\) はペアにできません。つまり、差分配列 \(d\) から \(M\) 個のインデックスを選ぶ際に、隣接する2つのインデックスを同時に選んではいけないという制約が付きます。

観察3: 素朴なDPでは不十分

DPで解くと \(O(NM)\) となり、\(N, M\) が最大 \(2 \times 10^5\) のとき間に合いません。

アルゴリズム

後悔付き貪欲法（Regret-based Greedy） を使います。

これは「隣接しない \(M\) 個の要素を選んで和を最小化する」問題の定番手法です。

基本アイデア

1. 最小ヒープに全ての \(d[i]\) を入れる
2. 最小値 \(d[i]\) を取り出して答えに加算する
3. \(d[i]\) を選んだので、隣接する \(d[i-1]\) と \(d[i+1]\) は選べなくなる → 削除する
4. 後悔用の要素として、値 \(d[i-1] + d[i+1] - d[i]\) を \(d[i]\) の位置に挿入する

なぜ後悔用要素を入れるのか？

後から「\(d[i]\) を選ばず、代わりに \(d[i-1]\) と \(d[i+1]\) を両方選んだ方が良かった」となる場合があります。後悔用要素 \(d[i-1] + d[i+1] - d[i]\) を選ぶことは、実質的に \(d[i]\) の選択を取り消し、\(d[i-1]\) と \(d[i+1]\) を選ぶことに相当します（コスト変化が \(d[i-1] + d[i+1] - d[i]\) だから）。

具体例

\(S = [1, 3, 4, 9, 10]\)、\(M = 2\) の場合： - \(d = [2, 1, 5, 1]\) - 最小は \(d[1] = 1\)。答え \(= 1\)。後悔用: \(d[0] + d[2] - d[1] = 2 + 5 - 1 = 6\) を挿入。\(d[3] = 1\) を削除しないよう注意（隣接は \(d[0]\) と \(d[2]\)）。 - 残り有効: 位置1の値6、\(d[3] = 1\)。最小は \(d[3] = 1\)。答え \(= 1 + 1 = 2\)。

結果：\((3,4)\) と \((9,10)\) をペアにして違和感合計 \(2\)。

データ構造

• 双方向連結リスト: 削除済み要素をスキップして左右の隣を \(O(1)\) で参照
• 最小ヒープ: 現在の最小値を効率的に取得（遅延削除で無効な要素をスキップ）

計算量

• 時間計算量: \(O(N \log N)\)（ソート + ヒープ操作各 \(O(\log N)\) を \(O(N)\) 回）
• 空間計算量: \(O(N)\)

実装のポイント

• 連結リストの番兵処理: 左端・右端で隣が存在しない場合、値を \(\infty\) として扱うことで、後悔用要素が境界で正しく計算される（片方の隣がなければ実質その方向への後悔は不可能）。

• 遅延削除: ヒープから取り出した要素が removed フラグで削除済みか、または値が更新されていないかを確認し、無効ならスキップする。

• 値の更新: 後悔用要素は同じインデックス位置に新しい値を上書きしてヒープに再追加することで、連結リスト上の位置を再利用する。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    S = [int(input_data[i + 2]) for i in range(N)]
    
    S.sort()
    
    # After sorting, optimal pairs are always adjacent elements.
    # We need to choose M non-overlapping adjacent pairs from N sorted elements
    # to minimize total difference.
    
    # Let d[i] = S[i+1] - S[i] for i = 0..N-2
    # We need to select M non-overlapping intervals of length 2 covering adjacent pairs.
    # This is equivalent to selecting M indices from d[0..N-2] such that no two selected
    # indices are consecutive, and minimizing the sum.
    
    # Wait, that's not quite right. If we pair (S[0],S[1]), that uses d[0].
    # If we pair (S[1],S[2]), that uses d[1]. These overlap (share S[1]).
    # If we pair (S[0],S[1]) and (S[2],S[3]), indices 0 and 2 in d - they are NOT consecutive,
    # so the constraint is: no two chosen indices in d are consecutive.
    
    # So: choose M indices from {0, 1, ..., N-2} with no two consecutive, minimize sum of d[chosen].
    
    # K = N-1 differences, choose M with no two adjacent.
    # This is feasible when M <= ceil(K/2) = ceil((N-1)/2).
    # Since M <= N/2, this is always feasible.
    
    # For small cases or when 2M = N or close, DP works.
    # But N can be 2*10^5, and we need efficient solution.
    
    # Classic approach: greedy with a linked list and priority queue (similar to the 
    # "choose M non-adjacent elements to minimize sum" problem).
    
    # Algorithm: Use a min-heap. When we pick element d[i], we must exclude d[i-1] and d[i+1].
    # But we add a "replacement" element d[i-1] + d[i+1] - d[i] which represents the option
    # of un-picking d[i] and instead picking d[i-1] and d[i+1].
    
    import heapq
    
    K = N - 1
    d = [S[i + 1] - S[i] for i in range(K)]
    
    # Linked list
    left = list(range(-1, K - 1))   # left[i] = i-1
    right = list(range(1, K + 1))   # right[i] = i+1
    # Sentinel values
    INF = float('inf')
    
    val = d[:]
    removed = [False] * K
    
    heap = [(d[i], i) for i in range(K)]
    heapq.heapify(heap)
    
    ans = 0
    
    for _ in range(M):
        # Pop minimum not removed
        while heap:
            v, idx = heapq.heappop(heap)
            if not removed[idx] and val[idx] == v:
                break
        
        ans += v
        
        # Get neighbors
        l = left[idx]
        r = right[idx]
        
        # New replacement value
        lv = val[l] if (0 <= l < K) else INF
        rv = val[r] if (0 <= r < K) else INF
        new_val = lv + rv - v
        
        val[idx] = new_val
        heapq.heappush(heap, (new_val, idx))
        
        # Remove left neighbor
        if 0 <= l < K:
            removed[l] = True
            ll = left[l]
            left[idx] = ll
            if 0 <= ll < K:
                right[ll] = idx
        
        # Remove right neighbor
        if 0 <= r < K:
            removed[r] = True
            rr = right[r]
            right[idx] = rr
            if 0 <= rr < K:
                left[rr] = idx
    
    print(ans)

solve()

---

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