\(A\) を昇順にしたとしても答えは変わりません。はじめに \(A\) を昇順にソートしたものとして考えます。

ここで、重要な事実としてペアの最大個数を達成する作り方のなかには、必ずすべての \(i\) について \(i\) 番目の靴下とペアを組んだものが \(i-1\) または \(i+1\) 番目であるような作り方が存在します。これは仮に \(i\) 番目の靴下と \(|j-i| \geq 2\) を満たす \(j\) 番目の靴下がペアとなったとき、適切な操作を繰り返すことで \(i\) と\(i-1\) または \(i+1\) 番目がペアになるよに言い換えることができるからです。いわゆる、Exchange Argument が適用できます。

そのため、次のような貪欲法で構成されるペアの作り方が最適となり、ペアの個数がこの問題における答えになります。

\(i=1,2,\ldots,N\) について

• \(i\) 番目の靴下がまだペアになっていないかつ \(|A_i-A_{i+1}|\leq K\) ならば \((i,i+1)\) をペアにする。

実装においてはfor文の中で、ペアを作るときに \(i\) をさらに \(+1\) するという操作をすることでまだペアになっていないかをいちいち判定する必要がなくなります。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& e : a) cin >> e;
    sort(a.begin(), a.end());
    int ans = 0;
    for (int i = 0; i + 1 < n; ++i) {
        if (a[i + 1] - a[i] <= k) {
            ans++;
            i++;
        }
    }
    cout << ans << endl;
}