概要

\(N\) 人のメンバーについて、実力（レーティング）では相手以下なのに自己評価では相手を超えていると過信している順序付きペア \((i, j)\) の総数を効率的に数える問題です。

考察

条件の整理

メンバー \(i\) がメンバー \(j\) を「見下している」条件は： - \(C_i > S_j\)（\(i\) の自己評価が \(j\) のレーティングより大きい） - \(S_i \leq S_j\)（\(i\) のレーティングは \(j\) のレーティング以下）

これを \(j\) の側から見ると、各 \(i\) に対して次を満たす \(j\)（\(j \neq i\)）を数えたいことになります：

\[S_i \leq S_j < C_i\]

つまり「\(S_j\) が \(S_i\) 以上かつ \(C_i\) 未満」である \(j\) の個数です。

重要な気づき

• \(C_i \leq S_i\) の場合、\(S_j \geq S_i\) かつ \(S_j < C_i\) を同時に満たす \(j\) は存在しないので、スキップできます。
• \(C_i > S_i\) の場合、\(j = i\) 自身も条件 \(S_i \leq S_i < C_i\) を満たしてしまうので、カウントから 1 を引く必要があります。

素朴なアプローチの問題

全ペア \((i, j)\) を調べると \(O(N^2)\) で、\(N \leq 2 \times 10^5\) では間に合いません。

解決策

\(S\) の値をソートしておけば、「\(S_i\) 以上 \(C_i\) 未満の \(S_j\) がいくつあるか」を二分探索で \(O(\log N)\) で求められます。

アルゴリズム

1. すべてのメンバーのレーティング \(S\) をソートした配列 S_sorted を用意する。
2. 各メンバー \(i\) について：
   • \(C_i \leq S_i\) ならスキップ（条件を満たす \(j\) は存在しない）。
   • そうでなければ、S_sorted 中で \([S_i, C_i)\) の範囲にある要素数を二分探索で求める。
     • lo = bisect_left(S_sorted, S_i) → \(S_i\) 以上の最初の位置
     • hi = bisect_left(S_sorted, C_i) → \(C_i\) 以上の最初の位置（\(C_i\) 未満の最後の次）
     • 個数は hi - lo
   • 自分自身 (\(j = i\)) を除くため 1 を引く。
3. すべての \(i\) の結果を合計して出力する。

具体例

例えば \(N = 3\)、\((S, C) = \{(5, 8), (7, 6), (3, 4)\}\) の場合： - S_sorted = [3, 5, 7] - \(i = 1\): \(S_1 = 5, C_1 = 8\)。\([5, 8)\) に含まれる \(S\) は \(\{5, 7\}\) → 2個、自分を引いて 1。 - \(i = 2\): \(S_2 = 7, C_2 = 6\)。\(C_2 \leq S_2\) なのでスキップ。 - \(i = 3\): \(S_3 = 3, C_3 = 4\)。\([3, 4)\) に含まれる \(S\) は \(\{3\}\) → 1個、自分を引いて 0。

答え: \(1\)

計算量

• 時間計算量: \(O(N \log N)\)（ソートに \(O(N \log N)\)、各メンバーの二分探索に \(O(\log N)\) × \(N\) 回）
• 空間計算量: \(O(N)\)（ソート済み配列の保持）

実装のポイント

• bisect_left(S_sorted, S_i) と bisect_left(S_sorted, C_i) を使うことで、半開区間 \([S_i, C_i)\) に含まれる要素数を正確に計算できます。

• \(C_i > S_i\) のとき、自分自身は必ず条件 \(S_i \leq S_i < C_i\) を満たすので、常に 1 を引けばよいです（場合分け不要）。

• 入力が大きいため sys.stdin.buffer.read() でまとめて読み込むと高速になります。

  ソースコード

import sys
from bisect import bisect_left, bisect_right, insort

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    S = [0] * N
    C = [0] * N
    for i in range(N):
        S[i] = int(input_data[idx]); idx += 1
        C[i] = int(input_data[idx]); idx += 1

    # Count ordered pairs (i, j) where:
    #   C_i > S_j  and  S_i <= S_j  and  i != j
    #
    # For each i, we need count of j such that:
    #   S_j >= S_i  and  S_j < C_i  and  j != i
    #
    # If C_i <= S_i, no valid j exists.
    # Otherwise, count j with S_i <= S_j < C_i, then subtract 1 if i itself satisfies S_i <= S_i < C_i
    # (which is always true when C_i > S_i, so always subtract 1).

    # Sort S values to use binary search
    S_sorted = sorted(S)

    ans = 0
    for i in range(N):
        si = S[i]
        ci = C[i]
        if ci <= si:
            continue
        # Count j with S_j >= si and S_j < ci
        lo = bisect_left(S_sorted, si)
        hi = bisect_left(S_sorted, ci)
        count = hi - lo
        # Subtract 1 for j == i (since si >= si and si < ci is true when ci > si)
        count -= 1
        ans += count

    print(ans)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。