概要

\(N\) 人の生徒の得点からなる数列 \(A\) が与えられたとき、得点の和が \(K\) 以上となる2人の生徒のペアの個数を求める問題です。

考察

すべてのペアを全探索する素朴なアプローチでは、二重ループが必要となり計算量は \(O(N^2)\) になります。今回の制約では \(N \leq 2 \times 10^5\) であるため、この方法では実行時間制限超過（TLE）となってしまいます。

ペアの個数を数えるだけであり、選ぶ要素の元の順番（出席番号）は関係ないため、まずは配列 \(A\) を昇順にソートすることを考えます。ソートされた配列において、両端から要素を見ていく「しゃくとり法（Two Pointers）」というテクニックを使うと、計算量を劇的に落とすことができます。

例えば、左端の要素 A[left] と右端の要素 A[right] の和が \(K\) 以上だったとします。配列は昇順に並んでいるため、A[left] よりも大きい A[left+1] や A[left+2] などと A[right] を足しても、必ず和は \(K\) 以上になります。 つまり、A[right] とペアにして \(K\) 以上になる相手は、left から right-1 までの right - left 人いることが一気に計算できます。

アルゴリズム

1. 生徒の得点配列 \(A\) を昇順（小さい順）にソートします。
2. 2つのポインタ left を \(0\) （配列の先頭）、right を \(N - 1\) （配列の末尾）に設定し、条件を満たすペアの数 ans を \(0\) で初期化します。
3. left < right を満たす間、以下の操作を繰り返します。
   • A[left] + A[right] \geq K の場合： A[left] から A[right-1] までのすべての要素が、A[right] との和で \(K\) 以上になります。そのため、ans に right - left を加算し、right を \(1\) 減らします（次に大きい要素を調べるため）。
   • A[left] + A[right] < K の場合： A[right] は現在の範囲で最大の要素ですが、それと足しても和が \(K\) に届かないため、これ以上 A[left] を使って条件を満たすペアは作れません。そのため、left を \(1\) 増やします。
4. 最終的な ans の値を出力します。

計算量

• 時間計算量: \(O(N \log N)\) 配列のソートに \(O(N \log N)\) かかります。その後のしゃくとり法（while ループ）では、各ステップで left が増えるか right が減るかのどちらかであり、最大でも \(N\) 回しかループが回らないため \(O(N)\) です。全体の時間計算量は \(O(N \log N)\) となり、制限時間内に余裕で間に合います。
• 空間計算量: \(O(N)\) 得点を格納するための配列 \(A\) を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• オーバーフローへの注意: 答えの最大値は、すべてのペアが条件を満たす場合の \(\frac{N(N-1)}{2}\) 通りです。\(N = 2 \times 10^5\) のとき、答えは約 \(2 \times 10^{10}\) となり、32ビット整数の上限（約 \(2 \times 10^9\)）を超えます。Pythonでは自動的に多倍長整数が使われるため気にする必要はありませんが、C++やJavaなどを用いる場合は、答えを格納する変数に64ビット整数型（long long など）を使用する必要があります。

• 高速な入出力: 入力される数値の個数が多いため、Pythonの場合は sys.stdin.read().split() などの高速な入力方法を用いることで、実行時間を安定して短縮できます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(x) for x in input_data[2:]]
    
    A.sort()
    
    ans = 0
    left = 0
    right = N - 1
    
    while left < right:
        if A[left] + A[right] >= K:
            ans += right - left
            right -= 1
        else:
            left += 1
            
    print(ans)

if __name__ == '__main__':
    main()

この解説は gemini-3.1-pro-thinking によって生成されました。