概要

\(N\) 人の生徒の得点が与えられ、任意の2人をペアにしたとき、その得点の合計が基準値 \(K\) 以上となるペアの個数を求めます。

考察

この問題は、全てのペア \((i, j)\)（\(i < j\)）について、\(A_i + A_j \geq K\) かどうかをチェックすれば解けますが、その方法では計算量が \(O(N^2)\) となり、\(N\) が最大 \(2 \times 10^5\) なので現実的ではありません（TLEになります）。

そこで、配列をソートしてから考えることにします。ソートしておくことで、「ある生徒 \(i\) に対して、それ以降のどの生徒 \(j\) とペアにすれば条件を満たせるか」を効率的に求めることができます。

具体的には、生徒 \(i\) の得点が \(A_i\) のとき、ペア相手の得点 \(A_j\) は少なくとも \(K - A_i\) 以上でなければなりません。ソートされた配列上で、この条件を満たす最小の \(j\)（ただし \(j > i\)）を二分探索で求めることができれば、そのような \(j\) より後ろにいるすべての生徒ともペアを作れるので、高速にカウントできます。

アルゴリズム

1. 生徒の得点リスト \(A\) を昇順にソートします。
2. 各生徒 \(i\)（\(0\) から \(N-2\) まで）に対して以下を行います：
   • ペア相手の得点の最低ライン：target = K - A[i]
   • この target 以上の値を持つ最小のインデックスを、\(A[i+1]\) 以降の範囲で二分探索（bisect_left）で求めます。
   • 見つかったインデックス pos から末尾までの人数（つまり \(N - \text{pos}\)）が、生徒 \(i\) とペアにして条件を満たす人数です。
3. 各 \(i\) に対する結果を合計して答えとします。

例

入力が以下の場合を考えてみましょう：

N = 5, K = 7
A = [1, 3, 5, 6, 8]

ソート後も同じ：[1, 3, 5, 6, 8]

• \(i=0\)（得点1）: 相手は6以上が必要 → 6, 8 → 2人
• \(i=1\)（得点3）: 相手は4以上が必要 → 5, 6, 8 → 3人
• \(i=2\)（得点5）: 相手は2以上が必要 → 5, 6, 8 → 3人
• \(i=3\)（得点6）: 相手は1以上が必要 → 6, 8 → 2人
• \(i=4\)（得点8）: もうペアにできる相手がいない → 0人

合計：2 + 3 + 3 + 2 + 0 = 10

計算量

• 時間計算量: \(O(N \log N)\)（ソートに \(O(N \log N)\)、ループ＋二分探索に \(O(N \log N)\)）
• 空間計算量: \(O(1)\)（入力以外の領域を使用しない）

実装のポイント

• 配列は必ずソートすること。

• 二分探索を行う範囲は、現在のインデックス \(i\) の次（\(i+1\)）以降にする必要がある（自分自身とはペアにできないため）。

• Pythonの bisect.bisect_left は、指定された範囲内で目的の値を挿入すべき場所を返すため、条件を満たす最小のインデックスを得られる。

  ソースコード

import bisect

N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

count = 0
for i in range(N):
    # A[i] + A[j] >= K となる最小の j を二分探索で求める
    target = K - A[i]
    # i+1 以降のインデックスで target 以上の要素の位置を探す
    pos = bisect.bisect_left(A, target, i + 1)
    count += N - pos

print(count)

---

この解説は qwen3-coder-480b によって生成されました。