概要

この問題は、与えられた \(N\) 枚の靴下から \(M\) 組のペアを作り、各ペアの「色の濃さの差（違和感）」の合計を最小化する問題です。

靴下の数 \(N\) および作りたいペアの数 \(M\) が最大で \(2 \times 10^5\) と大きいため、単純な動的計画法（DP）では間に合いません。そこで、WQS二分探索（通称：Alien DP）という高度な最適化手法を用いることで、高速に解を求めます。

---

考察

1. 靴下をソートする（隣接ペアの最適性）

直感的に、色の濃さが近い靴下同士をペアにするのが最適です。 靴下の色の濃さを昇順にソートした配列を \(A\) とします。このとき、最適なペアは必ずソート後の配列で隣り合う要素同士になります。

例えば、ソート後の靴下が \([1, 3, 4, 9]\) のとき： - 隣り合うペア \((1, 3)\) と \((4, 9)\) を作ると、違和感の合計は \(|1-3| + |4-9| = 2 + 5 = 7\) です。 - 交差するペア \((1, 9)\) と \((3, 4)\) を作ると、違和感の合計は \(|1-9| + |3-4| = 8 + 1 = 9\) となり、損をしてしまいます。

したがって、ソート後の配列において「隣り合う2つをペアにするか、あるいはペアにせず飛ばすか」を決めればよいことになります。

2. 素朴なDPとその限界

この問題は、以下の動的計画法（DP）で解くことができます。

• \(dp[i][j]\)：最初の \(i\) 枚の靴下から \(j\) 組のペアを作るときの、違和感の最小合計

遷移は以下の2つの選択肢の小さい方となります。 1. \(i\) 枚目の靴下をペアにしない： \(dp[i-1][j]\) 2. \(i\) 枚目の靴下を \(i-1\) 枚目の靴下とペアにする： \(dp[i-2][j-1] + (A[i-1] - A[i-2])\)

しかし、このDPの状態数は \(O(NM)\) です。\(N, M \le 2 \times 10^5\) であるため、状態数は最大で \(4 \times 10^{10}\) となり、実行時間制限（TLE）やメモリ制限（MLE）に引っかかってしまいます。

3. WQS二分探索（Alien DP）による次元削減

「ちょうど \(M\) 組選ぶ」という制約が原因でDPの次元が \(O(NM)\) に増えてしまっています。この制約を外すために、「ペアを1組作るたびに、ペナルティ（追加コスト） \(C\) がかかる」という新しい問題を考えます。

ペナルティ \(C\) を固定すると、ペアの個数を管理する必要がなくなるため、DPの次元を1つ減らすことができます。 - \(dp[i]\)：最初の \(i\) 枚の靴下を使い、ペナルティ \(C\) を考慮したときの最小コスト

遷移は以下のようになります。 1. \(i\) 枚目の靴下をペアにしない： \(dp[i-1]\) 2. \(i\) 枚目の靴下をペアにする： \(dp[i-2] + (A[i-1] - A[i-2] + C)\)

このDPは \(O(N)\) で高速に計算可能です。

ここで、ペナルティ \(C\) と作られるペアの数には以下の関係（単調性）があります。 - \(C\) を非常に大きくすると、ペアを作るコストが高すぎるため、ペアは \(0\) 組になります。 - \(C\) を非常に小さく（負の大きな値に）すると、ペアを作るほど全体のコストが下がるため、できるだけ多くのペアを作ろうとします。

この性質を利用して、作られるペアの数がちょうど \(M\) 組（またはそれ以上）になるようなギリギリのペナルティ \(C\) を二分探索で探索します。

---

アルゴリズム

1. ソート: 靴下の配列 \(S\) を昇順にソートします。
2. 二分探索: ペナルティ \(C\) の探索範囲を \([low, high] = [-2 \times 10^9, 2 \times 10^9]\) とします。
3. 判定関数（DP）:
   • 与えられた \(C\) に対して \(O(N)\) のDPを実行します。
   • DPの各要素には {最小コスト, そのコストを達成する際の最大ペア数} を持たせます。
   • コストが同じ場合は、できるだけペア数が多くなる方を優先します（タイブレーク）。
4. 二分探索の更新:
   • DPの結果得られたペア数が \(M\) 以上であれば、さらにペナルティ \(C\) を大きくしてペア数を減らせる可能性があるため、low = mid + 1 とし、その時点の \(mid\) を暫定の最適ペナルティ ans_C として記録します。
   • ペア数が \(M\) 未満であれば、ペナルティが大きすぎるため high = mid - 1 とします。
5. 答えの復元:
   • 最適なペナルティ ans_C を用いて再度DPを実行します。
   • 得られた最小コストは「違和感の合計 + \(M \times ans\_C\)」となっているため、ここから \(M \times ans\_C\) を引いた値が、ちょうど \(M\) 組のペアを作ったときの本来の違和感の最小合計になります。

---

計算量

• 時間計算量: \(O(N \log N + N \log(\max |S_i|))\)

  • ソートに \(O(N \log N)\) かかります。
  • 二分探索の回数は、ペナルティの探索範囲が約 \(4 \times 10^9\) であるため、およそ \(32\) 回です。各ステップで \(O(N)\) のDPを行うため、二分探索全体で \(O(N \log(\max |S_i|))\) となり、実行時間制限に十分間に合います。

• 空間計算量: \(O(N)\)

  • サイズ \(N\) の配列とDPテーブルを保持するため、空間計算量は \(O(N)\) であり、メモリ制限にも余裕で収まります。

---

実装のポイント

• タイブレークの処理: DPの遷移において、2つの選択肢のコストが等しい場合、ペアの数が多くなる方を選択します。これは、目的のペア数 \(M\) を確実に達成できる境界を見つけるために必要不可欠な処理です。

• ペナルティ \(C\) の符号: ペナルティ \(C\) は負の値（実質的なボーナス）になることもあります。そのため、二分探索の初期値 low は負の大きな値に設定する必要があります。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Solves the DP for a fixed penalty C.
// Returns {minimum_cost, maximum_pairs_achieving_this_cost}.
pair<long long, long long> solve_dp(long long C, const vector<long long>& A) {
    int n = A.size();
    vector<pair<long long, long long>> dp(n + 1);
    dp[0] = {0, 0};
    dp[1] = {0, 0};
    for (int i = 2; i <= n; ++i) {
        // Option 1: Do not pair the i-th sock
        auto res = dp[i-1];
        
        // Option 2: Pair the i-th sock with the (i-1)-th sock
        auto res2 = dp[i-2];
        res2.first += A[i-1] - A[i-2] + C;
        res2.second += 1;
        
        // Choose the option that minimizes cost, maximizing pairs as a tie-breaker
        if (res2.first < res.first) {
            dp[i] = res2;
        } else if (res2.first > res.first) {
            dp[i] = res;
        } else {
            dp[i] = (res2.second > res.second) ? res2 : res;
        }
    }
    return dp[n];
}

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    if (!(cin >> N >> M)) return 0;
    
    vector<long long> S(N);
    for (int i = 0; i < N; ++i) {
        cin >> S[i];
    }
    
    // Sort the socks by color intensity
    sort(S.begin(), S.end());
    
    // Binary search over the penalty C
    long long low = -2e9 - 7;
    long long high = 2e9 + 7;
    long long ans_C = low;
    
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        auto res = solve_dp(mid, S);
        if (res.second >= M) {
            ans_C = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    // Retrieve the answer using the optimal penalty ans_C
    auto res = solve_dp(ans_C, S);
    long long ans = res.first - M * ans_C;
    cout << ans << "\n";
    
    return 0;
}

---

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