概要

技術力の合計が \(X\) 以上、かつ体力の合計が \(Y\) 以上になる部員のペアを数えます。技術力でソートして候補を管理し、体力の条件を満たす人数を Fenwick Tree（BIT）で高速に求めます。

考察

1. 全ペアの確認では間に合わない

すべての組 \((i,j)\) を調べる方法では、時間計算量が \(O(N^2)\) になります。

\(N=10^5\) のとき、調べるペアは約 \(50\) 億組になるため、この方法では実行時間に間に合いません。

2. 技術力でソートすると、候補を追加するだけでよい

ある部員の技術力・体力を \((a,b)\) とすると、相手に必要な条件は次のとおりです。

• 技術力が \(X-a\) 以上
• 体力が \(Y-b\) 以上

ここで、部員を技術力の昇順にソートし、その順番で注目する部員を変えていきます。

注目する部員の技術力 \(a\) は減らないため、相手に必要な技術力 \(X-a\) は増えません。したがって、技術力の条件を満たす候補は増えるだけで、取り除く必要がありません。

例えば \(X=10\) の場合、注目する部員の技術力が \(3,5,7\) と増えると、相手に必要な技術力は \(7,5,3\) と下がります。

そこで、ソートした配列の末尾からポインタを動かし、技術力の条件を満たす部員を順にデータ構造へ追加します。

3. 体力の条件は Fenwick Tree で数える

技術力の条件を満たす候補の中から、さらに体力が \(Y-b\) 以上の人数を求めたいです。

これは、次の引き算で求められます。

\( \text{条件を満たす人数}=\text{候補の総人数}-\text{体力が }Y-b\text{ 未満の候補の人数} \)

Fenwick Tree は、各位置への個数の追加と、先頭からある位置までの個数の合計を、それぞれ \(O(\log N)\) で処理できます。

ただし、体力は最大 \(10^9\) なので、その値をそのまま配列の添字にはできません。体力の値を小さい順の番号に置き換える座標圧縮を行い、Fenwick Tree で管理します。

4. 自分自身と重複を補正する

この方法では、相手の候補を「自分より後ろの部員」に限定しません。そのため、次の補正が必要です。

• 自分自身も条件を満たすなら、その \(1\) 人分を引く。
• 異なる部員のペアは両方向から数えているので、最後に \(2\) で割る。

自分自身が数えられるのは、\(2a\ge X\) かつ \(2b\ge Y\) の場合です。

アルゴリズム

以降の添字は、技術力の昇順にソートした後の \(0\) 始まりの添字とします。並べ替えても、部員同士のペアとその条件は変わりません。

1. 部員を技術力の昇順にソートする。

2. 体力を座標圧縮する。

   • 全部員の体力を集め、ソートして重複を取り除いた配列 coordinates を作ります。
   • 各部員の体力がこの配列の何番目にあるかを b_index に保存します。

3. 候補を管理する変数を初期化する。

   • pointer = N - 1：次に候補へ追加する部員の位置
   • active = 0：追加済みの候補の人数
   • answer = 0：条件を満たす相手の人数の累計
   • Fenwick Tree：追加済みの候補を、圧縮後の体力ごとに数える

4. 部員を先頭から順に処理する。

注目する部員の技術力・体力を \((a,b)\) とします。

① 技術力の条件を満たす候補を追加する

pointer が指す部員について、\(A_{\text{pointer}}+a\ge X\) である間、次の処理を繰り返します。

• その部員の体力に対応する位置へ、Fenwick Tree で \(1\) を加算する。
• active を \(1\) 増やす。
• pointer を \(1\) 減らす。

ソート済みなので、この処理の終了時には、技術力の条件を満たす部員がちょうどすべて登録されています。

② 体力の条件も満たす人数を加算する

lower_bound を使い、coordinates の中で初めて \(Y-b\) 以上になる位置を below とします。

すると、圧縮後の添字が below 未満の値は、ちょうど体力が \(Y-b\) 未満の値です。したがって、

active - fenwick.prefix_sum(below)

を answer に加算します。

例えば、coordinates が \([2,5,8]\)、必要な体力が \(6\) なら、below は \(2\) です。体力 \(2,5\) の候補の人数を候補全体から引けば、体力 \(6\) 以上の候補の人数が得られます。

③ 自分自身を除外する

\(2a\ge X\) かつ \(2b\ge Y\) なら、自分自身が先ほどの人数に含まれるため、answer から \(1\) を引きます。

1. answer / 2 を出力する。

条件を満たす異なる部員のペアは、一方に注目したときと他方に注目したときの合計 \(2\) 回数えられています。そのため、\(2\) で割ると求めるペア数になります。

計算量

• 時間計算量: \(O(N\log N)\)
• 空間計算量: \(O(N)\)

ソートと座標圧縮に \(O(N\log N)\) かかります。pointer は減るだけなので、while 文による追加は全体で高々 \(N\) 回です。各追加と各部員に対する検索・集計は \(O(\log N)\) で処理できます。

実装のポイント

• 答えには 64 bit 整数を使う
  ペア数は最大で \(\frac{N(N-1)}{2}\) となり、32 bit 整数の範囲を超えます。また、最後に \(2\) で割る前の累計も大きくなるため、answer は long long にします。

• Fenwick Tree の区間の定義に注意する
  このコードの prefix_sum(count) は、圧縮後の添字が \(0\) 以上 count 未満の範囲の合計を返します。したがって、prefix_sum(below) は体力が \(Y-b\) 未満の人数になります。

• 境界値を含めるために lower_bound を使う
  必要なのは体力が \(Y-b\) 以上の人数です。ちょうど \(Y-b\) の部員を除外しないようにします。技術力についても比較は >= です。

• 同じ体力の部員も、それぞれ \(1\) 人として追加する
  座標圧縮では同じ値を同じ位置にまとめますが、Fenwick Tree には部員ごとに \(1\) を加算するため、人数は正しく数えられます。

• 自分自身の除外は、両方の条件を満たす場合だけ行う
  技術力だけ、または体力だけの条件を満たす場合には、もともと集計されていないので引いてはいけません。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

class FenwickTree {
    int n;
    vector<int> bit;

public:
    explicit FenwickTree(int n) : n(n), bit(n + 1, 0) {}

    void add(int index) {
        for (++index; index <= n; index += index & -index) {
            ++bit[index];
        }
    }

    int prefix_sum(int count) const {
        int result = 0;
        for (; count > 0; count -= count & -count) {
            result += bit[count];
        }
        return result;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long X, Y;
    cin >> N >> X >> Y;

    vector<pair<long long, long long>> members(N);
    vector<long long> coordinates;
    coordinates.reserve(N);

    for (auto& [a, b] : members) {
        cin >> a >> b;
        coordinates.push_back(b);
    }

    sort(members.begin(), members.end());
    sort(coordinates.begin(), coordinates.end());
    coordinates.erase(unique(coordinates.begin(), coordinates.end()),
                      coordinates.end());

    vector<int> b_index(N);
    for (int i = 0; i < N; ++i) {
        b_index[i] = lower_bound(coordinates.begin(), coordinates.end(),
                                 members[i].second) - coordinates.begin();
    }

    FenwickTree fenwick(static_cast<int>(coordinates.size()));
    int pointer = N - 1;
    int active = 0;
    long long answer = 0;

    for (int i = 0; i < N; ++i) {
        const auto [a, b] = members[i];

        while (pointer >= 0 && members[pointer].first + a >= X) {
            fenwick.add(b_index[pointer]);
            ++active;
            --pointer;
        }

        int below = lower_bound(coordinates.begin(), coordinates.end(), Y - b)
                    - coordinates.begin();
        answer += active - fenwick.prefix_sum(below);

        if (2 * a >= X && 2 * b >= Y) {
            --answer;
        }
    }

    cout << answer / 2 << '\n';
    return 0;
}

---

この解説は gpt-6-astra-medium によって生成されました。