概要

\(N\) 人の生徒から異なる2人を選ぶペアのうち、2人の得点の合計が基準値 \(K\) 以上となるペアの個数を効率的に数える問題です。

考察

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

最も単純な方法は、すべてのペア \((i, j)\)（\(i < j\)）について \(A_i + A_j \geq K\) かどうかを調べることです。しかし、ペアの総数は \(\frac{N(N-1)}{2}\) 個あり、\(N = 2 \times 10^5\) のとき約 \(2 \times 10^{10}\) 個になります。これでは時間制限に間に合いません（TLE）。

重要な気づき

条件 \(A_i + A_j \geq K\) を変形すると、\(A_j \geq K - A_i\) となります。つまり、ある生徒 \(i\) を固定したとき、もう一方の生徒の得点が \(K - A_i\) 以上であればよいということです。

配列をソートしておけば、\(K - A_i\) 以上の要素がどこから始まるかを二分探索で高速に求められます。これにより、各生徒 \(i\) に対して条件を満たす相手の人数を \(O(\log N)\) で求められます。

具体例

例えば \(N = 4\), \(K = 7\), \(A = [2, 5, 3, 8]\) の場合を考えます。

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

• \(i = 0\)（\(A_i = 2\)）: \(A_j \geq 7 - 2 = 5\) を満たす \(j > 0\) の個数 → \(A[2]=5, A[3]=8\) の2個
• \(i = 1\)（\(A_i = 3\)）: \(A_j \geq 7 - 3 = 4\) を満たす \(j > 1\) の個数 → \(A[2]=5, A[3]=8\) の2個
• \(i = 2\)（\(A_i = 5\)）: \(A_j \geq 7 - 5 = 2\) を満たす \(j > 2\) の個数 → \(A[3]=8\) の1個
• \(i = 3\)（\(A_i = 8\)）: \(j > 3\) の範囲に要素なし → 0個

合計: \(2 + 2 + 1 + 0 = 5\) 個

アルゴリズム

1. 配列 \(A\) を昇順にソートする。
2. 各 \(i = 0, 1, \ldots, N-1\) について以下を行う：
   • 閾値 \(\text{threshold} = K - A_i\) を計算する。
   • 配列 \(A\) の区間 \([i+1, N)\) において、\(A_j \geq \text{threshold}\) を満たす最小のインデックスを二分探索（bisect_left）で求める。このインデックスを \(\text{idx}\) とする。
   • 条件を満たすペアの個数は \(N - \text{idx}\) 個なので、これを答えに加算する。
3. 最終的な合計を出力する。

bisect_left(A, threshold, i+1, N) は、探索範囲を \(i+1\) 以降に限定することで、\(i < j\) の条件を自然に満たし、同じペアを二重に数えることを防ぎます。

計算量

• 時間計算量: \(O(N \log N)\)（ソートに \(O(N \log N)\)、各要素に対する二分探索に \(O(\log N)\) × \(N\) 回）
• 空間計算量: \(O(N)\)（配列の格納）

実装のポイント

• 探索範囲の指定: bisect_left の第3・第4引数で探索範囲を i+1 から N に限定することで、自分自身とのペアや重複カウントを防いでいます。

• 得点の値が最大 \(10^9\) で合計が最大 \(2 \times 10^9\): Python は多倍長整数を扱えるのでオーバーフローの心配はありませんが、C++ などでは long long を使う必要があります。

• 答えの型: ペア数は最大で \(\frac{N(N-1)}{2} \approx 2 \times 10^{10}\) になりうるため、32ビット整数では不足する点に注意が必要です（Python では問題なし）。

  ソースコード

import bisect

def main():
    import sys
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(input_data[i + 2]) for i in range(N)]
    
    A.sort()
    
    count = 0
    for i in range(N):
        # A[i] + A[j] >= K => A[j] >= K - A[i]
        threshold = K - A[i]
        # Find the leftmost index j in A where A[j] >= threshold, but j > i
        idx = bisect.bisect_left(A, threshold, i + 1, N)
        count += N - idx
    
    print(count)

main()

---

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