概要

各生徒の点数 \(A_i\) について、差の絶対値がちょうど \(K\) になる相手が「少なくとも1人」いる生徒が何人いるかを数えます。

考察

まず素朴に考えると、全ての組 \((i, j)\)（\(i \neq j\)）を調べて \(|A_i-A_j|=K\) を満たすか確認できますが、これは \(O(N^2)\) となり、\(N \le 2\times 10^5\) では間に合いません。

重要な気づきは次の通りです：

• 知りたいのは「条件を満たすペアの数」ではなく、「条件を満たす生徒の人数」です。
• 点数そのものに注目すると、生徒 \(i\) が条件を満たすためには
  \(A_i + K\) または \(A_i - K\) という点数を持つ別の生徒が存在すれば十分です。
• 同じ点数の生徒が複数いるので、点数ごとの人数（出現回数）を数えると効率化できます。

特に \(K=0\) は注意が必要です。
\(|A_i-A_j|=0\) なので「同じ点数の別人」が必要になります。つまり、点数 \(x\) の出現回数が \(2\) 以上なら、その点数の生徒全員が条件を満たします（1人しかいない点数は満たさない）。

例：\(A=[10,10,12]\), \(K=0\)
点数10が2人いるので、その2人は条件を満たすが、12は1人なので満たさない → 答えは2。

アルゴリズム

1. 点数配列 \(A\) について、各点数の出現回数を Counter（連想配列）で数える。
2. 場合分け：
   • \(K=0\) のとき
     出現回数が \(2\) 以上の点数について、その回数分を答えに加える。
     （同点の相手が存在するため、その点数の生徒は全員条件を満たす）
   • \(K>0\) のとき
     各点数 \(x\)（回数 \(v\)）について、cnt に \(x+K\) または \(x-K\) が存在すれば、その点数の生徒 \(v\) 人全員が条件を満たすので答えに \(v\) を加える。

これにより、生徒ごとに相手を探すのではなく、点数ごとの存在確認（\(O(1)\) 期待）で判定できます。

計算量

• 時間計算量: \(O(N)\)（Counter作成が \(O(N)\)、点数種類数を \(M\) として走査は \(O(M)\) で \(M \le N\)）
• 空間計算量: \(O(N)\)（点数の出現回数を保持）

実装のポイント

• \(K=0\) を必ず分けて処理する（\(x+K\) や \(x-K\) が同じ値になり、「自分以外」を正しく扱えないため）。

• Counter を使うと「点数 \(y\) が存在するか」を y in cnt で高速に判定できる。

• 入力は最大 \(2\times 10^5\) 要素なので、sys.stdin.buffer.read() による一括読み込みで高速化している。

  ソースコード

import sys
from collections import Counter

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    A = data[2:2+N]

    cnt = Counter(A)

    if K == 0:
        ans = sum(v for v in cnt.values() if v >= 2)
    else:
        ans = 0
        for x, v in cnt.items():
            if (x + K) in cnt or (x - K) in cnt:
                ans += v

    print(ans)

if __name__ == "__main__":
    main()

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