概要

実力（レーティング）は相手以下であるにもかかわらず、自己評価では相手の実力を超えていると過信している、という「見下している」ペア \((i, j)\) の総数を、二分探索を用いて高速に求める問題です。

考察

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

すべてのペア \((i, j)\) について条件を満たすかどうかを判定する素朴な方法（2重ループによる全探索）を考えてみます。 この場合、判定に \(O(N^2)\) の時間計算量がかかります。本問題では \(N \le 2 \times 10^5\) であるため、最悪の場合に約 \(4 \times 10^{10}\) 回の計算が必要となり、実行時間制限（通常 2 秒）に間に合わず TLE (Time Limit Exceeded) となってしまいます。

したがって、より効率的なアプローチが必要です。

2. 条件の整理

メンバー \(i\) を固定したとき、メンバー \(i\) がメンバー \(j\) を見下している条件は以下の通りです。 1. \(i \neq j\) 2. \(C_i > S_j\) 3. \(S_i \le S_j\)

これらを整理すると、メンバー \(j\) のレーティング \(S_j\) が以下の範囲にあることと同値になります。 - \(S_i \le S_j < C_i\) （かつ \(j \neq i\)）

つまり、各 \(i\) について、「全メンバーのレーティングのうち、 \(S_i\) 以上 \(C_i\) 未満であるものの個数」を高速に数え上げることができれば、この問題を解くことができます。

3. 二分探索による高速化

あらかじめ全メンバーのレーティングをソートした配列 \(A\) を用意しておきます。 ソートされた配列に対しては、二分探索（lower_bound）を用いることで、特定の範囲内にある要素の個数を \(O(\log N)\) で求めることができます。

具体的には、各 \(i\) について以下のように処理します。

• \(S_i \ge C_i\) のとき \(S_i \le S_j < C_i\) を満たす \(S_j\) は存在し得ないため、カウントは \(0\) です。
• \(S_i < C_i\) のとき ソートされた配列 \(A\) から、半開区間 \([S_i, C_i)\) に含まれる要素の個数を二分探索で求めます。
  • \(C_i\) 以上の最小の要素の位置（lower_bound(A.begin(), A.end(), C[i])）
  • \(S_i\) 以上の最小の要素の位置（lower_bound(A.begin(), A.end(), S[i])）

この 2 つの位置の差（要素数）を求めます。 ただし、この範囲には自分自身 \(S_i\) も含まれています（\(S_i < C_i\) より、自分自身は \(S_i \le S_i < C_i\) を満たすため）。 問題の条件には \(i \neq j\) があるため、求めた個数から自分自身の分の \(1\) を引いた値を答えに加算します。

アルゴリズム

1. 入力を受け取り、レーティングの配列 \(S\) と自己評価値の配列 \(C\) を保存する。
2. \(S\) をコピーした配列 \(A\) を作成し、昇順にソートする。
3. 答えを格納する変数 ans を \(0\) で初期化する。
4. 各 \(i = 0, 1, \dots, N-1\) について、以下を繰り返す：
   • \(S_i \ge C_i\) ならば、何もせず次のループへ進む。
   • \(S_i < C_i\) ならば：
     • 二分探索を用いて、配列 \(A\) の中で \(S_i\) 以上 \(C_i\) 未満の要素数 count を求める。
     • ans に count - 1 を加算する。
5. 最終的な ans の値を出力する。

計算量

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

  • レーティング配列のソートに \(O(N \log N)\) かかります。
  • 各メンバー \(i\) に対する二分探索（lower_bound）に \(O(\log N)\) かかり、これを \(N\) 回行うため、探索全体で \(O(N \log N)\) となります。
  • 全体として \(O(N \log N)\) となり、 \(N = 2 \times 10^5\) でも十分に実行時間制限内に間に合います。

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

  • 入力データおよびソート用の配列 \(A\) を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 型への配慮（オーバーフローの防止） 答えの最大値は、全員が全員を見下しているような極端なケースで \(N(N-1) \approx 4 \times 10^{10}\) に達します。これは 32bit 整数型（C++の int など）の最大値（約 \(2 \times 10^9\)）を超えるため、答えを保持する変数 ans は必ず 64bit 整数型（long long）を使用してください。

• 高速入出力 \(N\) のサイズが大きいため、C++では cin.tie(NULL) や ios_base::sync_with_stdio(false) を用いて入出力を高速化しておくことが推奨されます。

  ソースコード

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

using namespace std;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<long long> S(N), C(N);
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> S[i] >> C[i];
        A[i] = S[i];
    }

    // レーティングをソートして二分探索できるようにする
    sort(A.begin(), A.end());

    long long ans = 0;
    for (int i = 0; i < N; ++i) {
        // S_i >= C_i の場合、S_i <= S_j < C_i を満たす S_j は存在しない
        if (S[i] >= C[i]) {
            continue;
        }

        // A の中で [S_i, C_i) の範囲にある要素の個数を二分探索で求める
        auto it1 = lower_bound(A.begin(), A.end(), C[i]);
        auto it2 = lower_bound(A.begin(), A.end(), S[i]);
        long long count = distance(it2, it1);

        // S_i < C_i であるため、自分自身 (j = i) がカウントに含まれている。
        // i != j の条件を満たすため、1 を引く。
        ans += count - 1;
    }

    cout << ans << "\n";

    return 0;
}

---

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