概要

靴下の色の濃さ \(A_i\) を使い、差の絶対値が \(K\) 以下となるように 2 枚ずつペアを作るとき、作れるペア数の最大値を求めます。

考察

ペア条件は「2枚の差が \(K\) 以下」で、しかも靴下は使い回せません。最大個数を作るには「なるべく多くの靴下を無駄にしない組み方」が必要です。

ここで重要な観察は次の通りです：

• 靴下を色の濃さで 昇順にソートすると、近い値同士が隣に集まります。
• ソート後に、ある靴下 \(A[i]\) を誰かと組ませるなら、最も相性が良い候補は近い値（特に隣の \(A[i+1]\)）です。

素朴に「全ての組み合わせから最適なマッチングを探す」ようなことをすると、組み合わせは膨大（最大 \(2\times 10^5\) 枚）なので現実的に間に合いません（TLEになります）。

ではどうするかというと、ソートして左から順に見ていき、

• 隣同士 \(A[i], A[i+1]\) の差が \(K\) 以下なら この2枚をペアにする
• そうでなければ \(A[i]\) は 誰とも組めないので捨てて次へ

という貪欲法で最大を作れます。

なぜ「差が \(K\) を超えるとき \(A[i]\) を捨ててよい」のか？ - ソート済みなので、\(A[i+1]-A[i] > K\) なら、\(j>i+1\) に対しては \(A[j]\ge A[i+1]\) より \(A[j]-A[i] \ge A[i+1]-A[i] > K\) となり、後ろのどの靴下とも条件を満たせません。 - よって \(A[i]\) は必ず余るため、先へ進むのが最適です。

また、\(A[i+1]-A[i]\le K\) のとき隣同士でペアにしてよいのか？ - \(A[i]\) をより遠い相手（\(A[i+2]\) 以降）と組ませると、間の \(A[i+1]\) が余りやすくなり、ペア数が減る可能性が高いです。 - 隣同士で組むのが最も「詰めて」ペアを作れるため、結果的に最大個数になります。

具体例： - \(A=[1,2,10,11]\), \(K=1\) - \((1,2)\) は差1でOK → 1ペア - \((10,11)\) も差1でOK → 合計2ペア（最大）

• \(A=[1,3,4]\), \(K=1\)
  • \((1,3)\) は差2でNG → 1は誰とも組めないので捨てる
  • \((3,4)\) は差1でOK → 1ペア（最大）

アルゴリズム

1. 配列 \(A\) を昇順にソートする。
2. インデックス \(i=0\) から開始し、以下を繰り返す（\(i+1 < N\) の間）：
   • もし \(A[i+1]-A[i] \le K\) なら、\((A[i], A[i+1])\) をペアにして答えを \(+1\)、\(i\) を \(2\) 増やす（両方消費）。
   • そうでなければ \(A[i]\) はペアにできないので、\(i\) を \(1\) 増やす（\(A[i]\) を捨てる）。
3. 得られたペア数を出力する。

これは「ソート + 1回走査（2ポインタ的）」のシンプルな貪欲法です。

計算量

• 時間計算量: \(O(N\log N)\)（ソートが支配的、走査は \(O(N)\)）
• 空間計算量: \(O(N)\)（配列を保持。ソートも含めこの程度）

実装のポイント

• \(N\) が最大 \(2\times 10^5\) なので、入力は sys.stdin.buffer.read() などで高速に読むと安全です。

• ソート後は差分判定が \(A[i+1]-A[i]\) で済みます（昇順なので絶対値不要）。

• ループ条件を while i + 1 < N: にして、常に「次の要素が存在する」ことを保証します。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    A = data[2:]
    A.sort()
    i = 0
    ans = 0
    while i + 1 < N:
        if A[i + 1] - A[i] <= K:
            ans += 1
            i += 2
        else:
            i += 1
    print(ans)

if __name__ == "__main__":
    main()

---

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