概要

\(N\) 枚の靴下の中から、色の濃さの差が \(K\) 以内であるようなペアを最大で何組作れるかを求める問題です。

考察

この問題のポイントは、「どの靴下同士をペアにするのが最適か」を考えることです。

まず、色の濃さが近いもの同士をペアにするのが直感的によさそうです。例えば、色の濃さが \([10, 12, 13, 20]\) で \(K=5\) の場合を考えてみましょう。 - \(10\) と \(20\) をペアにしようとすると差が \(10\) なのでペアにできません。 - しかし、値が近い \(10\) と \(12\)、あるいは \(12\) と \(13\) を見ると、差が \(K\) 以下になっています。

このように、色の濃さを昇順（小さい順）に並べたとき、隣り合っている靴下は最も差が小さいため、ペアにできる可能性が最も高くなります。

貪欲法によるアプローチ

靴下をソートした状態 \(A_1, A_2, \dots, A_N\) で、左から順番に見ていきます。 1. \(A_1\) と \(A_2\) の差が \(K\) 以下なら、この 2 枚をペアにします。 - なぜなら、\(A_1\) を \(A_2\) 以外の靴下（\(A_3\) 以降）とペアにするメリットがないからです。\(A_1\) とペアにできる靴下があるなら、最も値が近い \(A_2\) と組ませておくのが、他の靴下を自由に使えるようにするために最善の選択となります。 2. もし \(A_1\) と \(A_2\) の差が \(K\) より大きい場合、\(A_1\) はどの靴下ともペアにできません。 - なぜなら、\(A_2\) 以降の靴下は \(A_2\) よりもさらに値が大きいため、差はさらに広がってしまうからです。したがって、\(A_1\) は諦めて次の \(A_2\) からのペアを考えます。

この「端から順番に、ペアにできるなら即座にペアにする」という貪欲法の考え方で、最大個数を求めることができます。

アルゴリズム

1. 靴下の色の濃さ \(A\) を昇順（小さい順）にソートします。
2. 左端の靴下から順番に、隣の靴下との差を確認していきます。
3. インデックス \(i = 0\) から始めて、以下の処理を繰り返します：
   • \(A_{i+1} - A_i \le K\) ならば：
     • ペアが 1 つ作れるので、カウントを \(+1\) します。
     • 使った靴下はもう使えないので、次は \(i+2\) 番目の靴下を確認します。
   • \(A_{i+1} - A_i > K\) ならば：
     • \(A_i\) は誰ともペアになれないので、次は \(i+1\) 番目の靴下を確認します。
4. 最終的なカウントを出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 靴下のソートに \(O(N \log N)\) かかります。その後のリストの走査は \(O(N)\) なので、全体ではソートの計算量が支配的になります。
• 空間計算量: \(O(N)\)
  • 入力された靴下のデータを保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• \(N\) が最大 \(2 \times 10^5\) と比較的大きいため、Python では sys.stdin.read().split() などを用いて高速に入力を読み込むと安全です。

• ペアが成立したときにインデックスを \(2\) 進め、成立しなかったときに \(1\) 進める処理は、while ループを使うと簡潔に記述できます。

  ソースコード

import sys

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    a = list(map(int, input_data[2:]))
    
    # 靴下の色の濃さを昇順にソート
    a.sort()
    
    ans = 0
    i = 0
    # 隣り合う靴下を確認していく貪欲法
    while i < n - 1:
        # 差が K 以下であればペアにする
        if a[i+1] - a[i] <= k:
            ans += 1
            # ペアにしたので次の靴下は2つ先から確認
            i += 2
        else:
            # ペアにできなかったので次の靴下へ
            i += 1
            
    print(ans)

if __name__ == "__main__":
    solve()

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