概要

\(N\) 人の部員の中から 2 人のペア \((i, j)\) を選ぶとき、技術力の合計が \(X\) 以上かつ体力の合計が \(Y\) 以上となる組み合わせの総数を求める問題です。

考察

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

すべての部員のペア \((i, j)\) （\(1 \le i < j \le N\)）を全探索し、条件 \(A_i + A_j \ge X\) かつ \(B_i + B_j \ge Y\) を満たすか確認する方法がまず考えられます。 しかし、選ぶペアの総数は \(\frac{N(N - 1)}{2} \approx \frac{10^{10}}{2} = 5 \times 10^9\) 通り存在するため、計算量は \(O(N^2)\) となり、実行時間制限に間に合わず TLE (実行時間制限超過) となります。

効率的な数え上げへの変形

条件を部員 \(i\) と部員 \(j\) について整理すると、次のようになります。 - \(A_j \ge X - A_i\) - \(B_j \ge Y - B_i\)

これは、「部員 \(i\) の条件を満たす部員 \(j\) が何人いるか」という 2次元の範囲クエリ（多次元部分空間の点数え上げ） の問題と捉えることができます。 2つの条件を同時に満たすペアを高速に数えるためには、片方の条件（\(A\) に関する条件）をソートなどで順序付けし、もう片方の条件（\(B\) に関する条件）をデータ構造（BIT など）で管理する手法が典型的です。

さらに、インデックスの順序関係（\(i < j\)）を保ったまま処理するために、分割統治法（CDQ分治） を利用するのが非常に効果的です。

アルゴリズム

本解法では、分割統治法 と Binary Indexed Tree (BIT)、および 座標圧縮 を組み合わせて解きます。

1. 座標圧縮

\(B_i\) や \(Y - B_i\) は最大で \(2 \times 10^9\) と非常に大きいため、そのまま配列の添字としては扱えません。 出現するすべての \(B_i\) と \(Y - B_i\) の値（高々 \(2N\) 個）を重複なくソートし、それぞれの値が何番目に小さいか（座圧後のインデックス）を求めておきます。

2. 分割統治法（CDQ分治）

区間 \([l, r)\) 内のペアを数える関数 solve(l, r) を考えます。 中央を \(m = \lfloor (l + r) / 2 \rfloor\) としたとき、ペア \((i, j)\) は以下の 3 通りに分類できます。 1. \(l \le i < j < m\) （左半分に両方含まれる） \(\to\) 再帰呼び出し solve(l, m) 2. \(m \le i < j < r\) （右半分に両方含まれる） \(\to\) 再帰呼び出し solve(m, r) 3. \(l \le i < m \le j < r\) （左に \(i\)、右に \(j\) がある）

この「3. 左に \(i\)、右に \(j\) がまたがるペア」の個数を効率よく数え上げます。

3. 平面走査と BIT による数え上げ

\(l \le i < m \le j < r\) について、満たすべき条件は \(A_j \ge X - A_i\) かつ \(B_j \ge Y - B_i\) です。 これを「イベント」として扱い、次のように分類します。 - 点の追加イベント（右側 \(j\)）: 値 \(A_j\)、座標 \(B_j\) - クエリイベント（左側 \(i\)）: 値 \(X - A_i\)、条件 \(\ge Y - B_i\)

これらを第 1 キー（値）の降順でソートして走査します。 1. 値が大きい順に見ることで、クエリ \(X - A_i\) を処理する時点では、すでに \(A_j \ge X - A_i\) を満たす右側の要素 \(j\) のみが BIT に追加されている状態を作れます。 2. BIT には \(B_j\) の座標位置に \(+1\) していきます。 3. クエリ \(i\) が来たら、BIT 内の「\(Y - B_i\) 以上の個数」を取得して答えに加算します。 4. 全ての処理が終わったら、BIT を次の計算のために元の状態（すべて 0）に戻します。

計算量

• 時間計算量: \(O(N \log^2 N)\)
  • 座標圧縮に \(O(N \log N)\) かかります。
  • 分割統治の再帰の深さは \(O(\log N)\) です。
  • 各深さにおいて、長さ \(K\) の区間ごとにイベントのソートに \(O(K \log K)\)、BIT 操作に \(O(K \log N)\) かかります。1つの深さ全体の区間長の合計は \(N\) なので、各層で \(O(N \log N)\) となり、全体で \(O(N \log^2 N)\) です。\(N = 10^5\) でも十分に制限時間内に間に合います。
• 空間計算量: \(O(N)\)
  • 座標圧縮用の配列や BIT、再帰のコールスタックを含めて \(O(N)\) のメモリで動作します。

実装のポイント

• 降順ソート時のタイブレーク: \(A_j = X - A_i\) となる境界値のケースでは、クエリの前に点の追加を行う必要があります。 追加イベントを type = 1、クエリイベントを type = 0 と定義してタプル (値, type, ...) を降順ソートすることで、値が等しい場合に自然と type = 1（追加）が先に来るよう工夫されています。

• BIT の初期化方法: 分割統治の各ステップで BIT を bit = [0] * M などと全体初期化してしまうと、初期化だけで \(O(N^2)\) の時間がかかってしまいます。追加したインデックスをリストに記録しておき、加算した分だけ減算して \(0\) に戻すことで、計算量を増やさずに再利用しています。

• Python の再帰深度: 分割統治法の再帰呼び出しが深くなる可能性があるため、sys.setrecursionlimit で上限を引き上げておく必要があります。

  ソースコード

import sys
import bisect

# 再帰深度の上限を増やす
sys.setrecursionlimit(300000)

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    X = int(data[1])
    Y = int(data[2])
    
    A = [0] * N
    B = [0] * N
    ptr = 3
    for i in range(N):
        A[i] = int(data[ptr])
        B[i] = int(data[ptr+1])
        ptr += 2
        
    vals = sorted(list(set(B + [Y - b for b in B])))
    M = len(vals)
    
    B_comp = [bisect.bisect_left(vals, b) for b in B]
    Y_B_comp = [bisect.bisect_left(vals, Y - b) for b in B]
    
    bit = [0] * (M + 2)
    
    def solve(l, r):
        if r - l <= 1:
            return 0
        m = (l + r) // 2
        ans = solve(l, m) + solve(m, r)
        
        # R の点イベント (type=1) と L のクエリイベント (type=0)
        events = [(A[j], 1, B_comp[j]) for j in range(m, r)] + [(X - A[i], 0, Y_B_comp[i]) for i in range(l, m)]
        events.sort(reverse=True)
        
        total_added = 0
        added = []
        step_ans = 0
        
        for val, type_, b_val in events:
            if type_ == 1:
                total_added += 1
                idx = b_val + 1
                added.append(idx)
                while idx <= M:
                    bit[idx] += 1
                    idx += idx & (-idx)
            else:
                if b_val == 0:
                    step_ans += total_added
                else:
                    s = 0
                    idx = b_val
                    while idx > 0:
                        s += bit[idx]
                        idx -= idx & (-idx)
                    step_ans += total_added - s
                    
        for idx in added:
            while idx <= M:
                bit[idx] -= 1
                idx += idx & (-idx)
                
        return ans + step_ans

    ans = solve(0, N)
    print(ans)

if __name__ == '__main__':
    main()

---

この解説は gemini-3.8-flash-high によって生成されました。