概要

\(N\) 枚の靴下を、色の濃さの差が \(K\) 以下になるようにペアにするとき、作れるペアの最大個数を求める問題です。

考察

重要な気づき

まず、靴下をペアにする条件は「色の濃さの差が \(K\) 以下」です。これは差の絶対値なので、近い値同士をペアにすることが重要になります。

素朴なアプローチの問題点

全ての靴下のペアの組み合わせを試す方法を考えると、\(N\) 枚から2枚を選ぶ組み合わせは \(\binom{N}{2} = \frac{N(N-1)}{2}\) 通りあります。さらに、どのペアを選ぶかの最適化も必要になり、計算量が膨大になってしまいます。

解決の糸口：ソート + 貪欲法

靴下を色の濃さでソートすると、ペアにできる可能性があるのは「近くにある靴下同士」に限られます。

例: \(K = 2\) のとき、靴下の色の濃さが \([1, 3, 5, 6, 8]\) だとします。 - \(1\) と \(3\) の差は \(2\) → ペア可能 - \(5\) と \(6\) の差は \(1\) → ペア可能 - \(8\) は余る - 結果: 2ペア

なぜ隣同士を貪欲にペアにするのが最適か？

ソート後、左から順に見ていき、隣の靴下とペアにできるならペアにする戦略が最適です。

理由: ある靴下 \(A[i]\) をペアにする相手として、\(A[i+1]\) より遠くの \(A[i+2]\) を選んだとします。すると \(A[i+1]\) が余ってしまい、\(A[i+1]\) は \(A[i]\) または \(A[i+2]\) としかペアになれない可能性があります。できるだけ近いもの同士をペアにした方が、後の選択肢を広く残せるのです。

アルゴリズム

1. 靴下の色の濃さの配列 \(A\) を昇順にソートする
2. インデックス \(i = 0\) から始めて、左から順に処理する
3. \(A[i+1] - A[i] \leq K\) なら、\(i\) 番目と \(i+1\) 番目をペアにして、\(i\) を \(2\) 進める
4. そうでなければ、\(i\) 番目はスキップして、\(i\) を \(1\) 進める
5. 作成したペアの個数を出力する

具体例: \(N=5\), \(K=2\), \(A=[3, 1, 6, 5, 8]\)

ソート後: \(A = [1, 3, 5, 6, 8]\)

\(i\)	比較	差	判定	操作	ペア数
0	\(A[1] - A[0] = 3 - 1\)	2	\(\leq K\)	ペア成立、\(i \to 2\)	1
2	\(A[3] - A[2] = 6 - 5\)	1	\(\leq K\)	ペア成立、\(i \to 4\)	2
4	\(i = N-1\) でループ終了

答え: 2

計算量

• 時間計算量: \(O(N \log N)\)（ソートがボトルネック。貪欲法のループは \(O(N)\)）
• 空間計算量: \(O(N)\)（配列 \(A\) の保持）

実装のポイント

• ソート後は隣同士の差だけを見ればよいので、A[i+1] - A[i] の計算で絶対値を取る必要がない（ソートにより必ず \(A[i+1] \geq A[i]\)）

• ペアを作った場合は i += 2、作らなかった場合は i += 1 という増分の違いに注意

• while i < N - 1 で終了条件を設定し、最後の1枚だけ残った場合は自動的にループを抜ける

  ソースコード

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # ソートして貪欲法で解く
    A.sort()
    
    # 貪欲法: 左から順に、ペアにできるなら隣同士をペアにする
    # これが最適である理由: ソート後、できるだけ近いもの同士をペアにした方が
    # 後の選択肢を残せる
    
    pairs = 0
    i = 0
    while i < N - 1:
        if A[i + 1] - A[i] <= K:
            pairs += 1
            i += 2  # 両方使用済み
        else:
            i += 1  # 現在の靴下は後でペアにできる可能性を探る
    
    print(pairs)

solve()

---

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