公式

E - ペアの選定 / Choosing Pairs 解説 by admin

Gemini 3.8 Flash (High)

概要

\(N\) 人の部員の中から、\(A_i + A_j \ge X\) かつ \(B_i + B_j \ge Y\) を満たすペア \((i, j)\) (\(i < j\)) の個数を求める問題です。2次元の領域内にある点の個数を数え上げる問題に帰着し、平面走査と Fenwick Tree（Binary Indexed Tree）を用いて高速に解くことができます。

考察

素朴なアプローチとその限界

すべてのペア \((i, j)\) の組み合わせ（全部で \(\frac{N(N-1)}{2}\) 通り）について条件を満たすか判定する方法がまず考えられます。しかし、今回の制約は \(N \le 10^5\) であるため、ペアの数は約 \(5 \times 10^9\) 通りとなり、実行時間制限（通常2〜3秒）に到底間に合わず TLE (Time Limit Exceeded) となってしまいます。したがって、\(O(N \log N)\) 程度で動作する効率的なアルゴリズムが必要です。

幾何的な問題への言い換え

条件式を変形してみましょう。ある部員 \(i\) を固定したとき、ペアの相手となる部員 \(j\) が満たすべき条件は以下の2つです。 - \(A_j \ge X - A_i\) - \(B_j \ge Y - B_i\)

これは、各部員 \(j\) を 2 次元平面上の点 \((A_j, B_j)\) とみなしたとき、「\(x \ge X - A_i\) かつ \(y \ge Y - B_i\) を満たす点 \((A_j, B_j)\) の個数を数える」 という2次元の範囲検索クエリになります。

すべてのペアを求める問題ですが、各 \(i\) に対して「自分とペアを組める \(j\) の人数」を数え上げ、後から重複（\(i\) と \(j\) の順序、および \(i = j\) の自分自身）を補正すれば、元の問題を解くことができます。

平面走査（スイープライン）の利用

2次元の条件を同時に扱うのは難しいため、片方の次元（\(x\) 座標）をイベントのソートで処理し、もう片方の次元（\(y\) 座標）をデータ構造で管理する平面走査法を適用します。

  1. \(x\) 座標について、値が大きい順に見ていく（降順）。
  2. 点 \((A_j, B_j)\) を追加するイベントと、クエリ \((X - A_i, Y - B_i)\) を評価するイベントを用意する。
  3. \(x\) 座標が大きいものから順に処理していくことで、「現在見ているクエリの \(x\) 座標以上の点」のみがデータ構造に入っている状態を作れます。
  4. あとはデータ構造側で「\(y\) 座標が \(Y - B_i\) 以上の点の個数」を高速に取得できればよいです。

\(y\) 座標の値は最大で \(2 \times 10^9\) と非常に大きいため、登場する値をあらかじめ座標圧縮しておき、Fenwick Tree を使うことで \(1\) 回あたり \(O(\log N)\) で値の追加と区間和の取得が可能です。

アルゴリズム

  1. 座標圧縮:

    • \(y\) 座標に関係する値は各部員の \(B_i\) と \(Y - B_i\) の高々 \(2N\) 種類です。これらを昇順にソートして重複を削除し、各値に \(1\) から始まるランク（ID）を割り当てます。

  2. イベントの作成とソート:

    • 点追加イベント: 部員 \(j\) について、\((x = A_j, \text{type} = \text{点}, y\text{のID} = \text{id}(B_j))\)
    • クエリエベント: 部員 \(i\) について、\((x = X - A_i, \text{type} = \text{クエリ}, y\text{のID} = \text{id}(Y - B_i), \text{部員番号} = i)\)
    • これら \(2N\) 個のイベントを \(x\) 座標の降順にソートします。
    • ※ \(x\) 座標が等しい場合は、クエリを処理する前に点を追加する必要があるため、「点」を「クエリ」よりも先に処理するようにします。

  3. 走査とクエリ処理:

    • Fenwick Tree を空の状態で用意します。
    • ソートしたイベントを先頭から順に走査します。
      • 点追加イベント: その点の \(y\) の ID の位置に \(+1\) を加算します。
      • クエリエベント: Fenwick Tree を使って、\([y\text{のID}, \text{最大ID}]\) の区間に入っている点の合計数を求め、部員 \(i\) のペア候補数 \(cnt[i]\) として記録します。

  4. 重複の除外と答えの計算:

    • 求めた \(cnt[i]\) には、自分自身（\(j = i\)）が含まれている可能性があります。\(2A_i \ge X\) かつ \(2B_i \ge Y\) を満たす場合は、自分自身を数えてしまっているため \(cnt[i]\) から \(1\) を引きます。
    • すべての \(i\) について \(cnt[i]\) を合計すると、各ペア \((i, j)\) が \((i, j)\) と \((j, i)\) として \(2\) 回ずつカウントされているため、合計を \(2\) で割った値を出力します。

計算量

  • 時間計算量: \(O(N \log N)\)
    • 座標圧縮のためのソート: \(O(N \log N)\)
    • イベントのソート: \(O(N \log N)\)
    • イベント走査および Fenwick Tree の操作（\(2N\) 回、各 \(O(\log N)\)）: \(O(N \log N)\)
    • 全体として \(O(N \log N)\) となり、実行時間制限に余裕で間に合います。
  • 空間計算量: \(O(N)\)
    • イベント配列、Fenwick Tree、座標圧縮用の配列などに必要なメモリはすべて要素数 \(O(N)\) です。

実装のポイント

  • タイブレーク（順序の決定）:

    • \(A_j = X - A_i\) のように \(x\) 座標が同じ値を持つ場合、問題の条件は「\(A_i + A_j \ge X\)」と等号を含むため、点追加をクエリ処理よりも先に行う必要があります。イベントをソートする際の比較関数で type の優先順位を適切に設定します。

  • オーバーフローへの注意:

    • \(X, Y, A_i, B_i\) は最大 \(10^9\) または \(2 \times 10^9\) であるため、自分自身の判定 2 * A[i] >= X や合計ペア数の計算では 64bit 整数型（C++ の long long）を使用してください。

      ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
struct Fenwick {
    int n;
    vector<T> tree;
    Fenwick(int n) : n(n), tree(n + 1, 0) {}
    void add(int i, T delta) {
        for (; i <= n; i += i & -i) tree[i] += delta;
    }
    T query(int i) {
        T sum = 0;
        for (; i > 0; i -= i & -i) sum += tree[i];
        return sum;
    }
    T query(int l, int r) {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }
};

struct Event {
    long long x;
    int type; // 1: point, 0: query
    int y_id;
    int id;
};

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

    int n;
    long long x_req, y_req;
    if (!(cin >> n >> x_req >> y_req)) return 0;

    vector<long long> a(n), b(n);
    vector<long long> vals;
    vals.reserve(2 * n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        vals.push_back(b[i]);
        vals.push_back(y_req - b[i]);
    }

    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    auto get_id = [&](long long v) {
        return lower_bound(vals.begin(), vals.end(), v) - vals.begin() + 1;
    };

    int m = vals.size();
    vector<Event> events;
    events.reserve(2 * n);

    for (int i = 0; i < n; ++i) {
        events.push_back({a[i], 1, get_id(b[i]), -1});
        events.push_back({x_req - a[i], 0, get_id(y_req - b[i]), i});
    }

    sort(events.begin(), events.end(), [](const Event& e1, const Event& e2) {
        if (e1.x != e2.x) return e1.x > e2.x;
        return e1.type > e2.type;
    });

    Fenwick<int> ft(m);
    vector<int> cnt(n, 0);

    for (const auto& e : events) {
        if (e.type == 1) {
            ft.add(e.y_id, 1);
        } else {
            cnt[e.id] = ft.query(e.y_id, m);
        }
    }

    long long total_pairs = 0;
    for (int i = 0; i < n; ++i) {
        if (2LL * a[i] >= x_req && 2LL * b[i] >= y_req) {
            cnt[i]--;
        }
        total_pairs += cnt[i];
    }

    cout << total_pairs / 2 << "\n";

    return 0;
}

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