概要

異なる2人の生徒の得点の合計が基準値 \(K\) 以上となるペアの数を求める問題です。

考察

素朴なアプローチとして、全てのペア \((i, j)\)（\(i < j\)）を調べ、\(A_i + A_j \geq K\) かどうかを判定する方法が考えられます。しかし、この方法の時間計算量は \(O(N^2)\) であり、\(N\) が最大 \(2 \times 10^5\) という制約では、約 \(2 \times 10^{10}\) 回の計算が必要となり、実行時間制限に間に合いません。

そこで、より効率的な方法を考える必要があります。配列をソートすることで、特定の条件を満たすペアを高速に数え上げる手法が有効です。ソート後、しゃくとり法や二分探索を用いることで、効率的に条件を満たすペアの数を求めることができます。

アルゴリズム

1. 配列 \(A\) をソートします。
2. しゃくとり法を用いて、条件を満たすペアの数を数えます。
   • 左ポインタ left を先頭に、右ポインタ right を末尾に設定します。
   • A[left] + A[right] >= K の場合:
     • このとき、left から right-1 までの全ての要素と right を組にすると条件を満たします（合計値は A[left] + A[right] 以上になるため）。よって、(right - left) 個のペアが条件を満たすことになります。
     • その後、right をデクリメントして、次の大きい値の組み合わせを調べます。
   • 条件を満たさない場合:
     • left をインクリメントして、合計値を大きくします。
3. この操作を left < right の間繰り返します。

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)、しゃくとり法の処理に \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 配列 \(A\) を格納するためのメモリが必要です。

実装のポイント

• ソートすることで、しゃくとり法を適用できるようになります。

• 条件を満たす場合のペアの数え方に注意します。right - left で現在の right と組にできる left 以降の全ての要素のペアを数えています。

• ポインタの更新を正しく行うことが重要です。条件を満たすときは right を減らし、満たさないときは left を増やします。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+n]))
    A.sort()
    
    count = 0
    left = 0
    right = n - 1
    
    while left < right:
        if A[left] + A[right] >= K:
            count += (right - left)
            right -= 1
        else:
            left += 1
            
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。