概要

得点配列 \(A\) から異なる 2 人 \((i,j)\) を選び、\(A_i + A_j \ge K\) を満たすペアの個数を数えます。ソート＋2ポインタで全ペアを高速に数え上げます。

考察

素朴には全ての組 \((i,j)\)（\(1 \le i < j \le N\)）を調べればよく、計算量は \(O(N^2)\) です。しかし \(N \le 2 \times 10^5\) なので、最大で約 \(2 \times 10^{10}\) 組となり到底間に合いません（TLE）。

そこで重要な観察は次の 2 つです。

• 得点を昇順にソートすると、「小さい値＋大きい値」の大小関係が単調になります。
• ある右端の要素 \(A[r]\) に対して、\(A[l] + A[r] \ge K\) が成り立つなら、\(l\) より右側の全ての \(i\)（\(l < i < r\)）でも \(A[i] \ge A[l]\) なので
  \(A[i] + A[r] \ge A[l] + A[r] \ge K\) が必ず成り立ちます。

つまり、条件を満たすかどうかを 1 組ずつ調べなくても、「まとめて数える」ことができます。

例：\(A=[1,3,4,8]\)（ソート済み）, \(K=10\)
\(r=3\)（値 8）, \(l=1\)（値 3）で \(3+8 \ge 10\) なら、\((1,3)\) だけでなく \((2,3)\)（\(4+8\)）も確実に条件を満たすので一気に 2 個数えられます。

アルゴリズム

1. 配列 \(A\) を昇順にソートする。
2. 2 つのポインタ \(l=0\)（左端）, \(r=N-1\)（右端）を用意する。
3. \(l<r\) の間、以下を繰り返す：
   • もし \(A[l] + A[r] \ge K\) なら
     \(r\) を固定したとき、左側の候補は \(l, l+1, \dots, r-1\) の全てが条件を満たす。
     よってペア数に \((r-l)\) を加え、次に \(r\) を 1 減らす（\(r \leftarrow r-1\)）。
   • そうでなければ（\(A[l] + A[r] < K\)）
     この \(l\) ではどんなに右を選んでも（右は最大でも \(r\)）条件を満たせないので、\(l\) を 1 増やす（\(l \leftarrow l+1\)）。
4. 加算した合計が答え。

この方法では、各ポインタが片方向に最大 \(N\) 回ずつ動くだけなので、ソート後の部分は \(O(N)\) で済みます。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的、2ポインタ部分は \(O(N)\)）
• 空間計算量: \(O(N)\)（配列を保持）

実装のポイント

• 条件 \(A[l] + A[r] \ge K\) を満たしたときに加えるのは「1」ではなく「\((r-l)\)」である点が肝です（まとめて数える）。

• \(l<r\) を保つ（同じ生徒を 2 回使わない）ようにループ条件を while l < r: にします。

• 答えは最大で \(\binom{N}{2}\) となり得るため、言語によっては 64bit 整数が必要です（Python なら自動で大丈夫）。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    k = int(data[1])
    a = list(map(int, data[2:2+n]))
    a.sort()

    l, r = 0, n - 1
    ans = 0
    while l < r:
        if a[l] + a[r] >= k:
            ans += (r - l)
            r -= 1
        else:
            l += 1

    print(ans)

if __name__ == "__main__":
    main()

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