概要

各メンバー \(i\) について「相手の実力 \(S_j\) は自分以上（\(S_i \le S_j\)）なのに、自己評価 \(C_i\) では相手より上（\(C_i > S_j\)）」となる相手 \(j\) の人数を数え、全員分を合計します。

考察

「見下している」条件 - \(i \ne j\) - \(C_i > S_j\) - \(S_i \le S_j\)

をまとめると、相手 \(j\) のレーティング \(S_j\) が

[ S_i \le S_j < C_i ]

を満たす必要があります。つまり、\(i\) に対して必要なのは「\(S_j\) がある区間に入る人数」だけで、\(j\) 側の自己評価 \(C_j\) は一切関係ありません。

素朴解がダメな理由

各 \(i\) について全員 \(j\) を調べると \(O(N^2)\) です。
\(N \le 2\times 10^5\) なので、最大で約 \(4\times 10^{10}\) 回比較となり現実的に間に合いません。

どう解決するか

必要なのは「値 \(S_j\) が区間 \([S_i, C_i)\) に入る個数」なので、全員の \(S\) をソートしておけば、二分探索で

• \(S_j \ge S_i\) となる最初の位置
• \(S_j \ge C_i\) となる最初の位置

を求め、その差で区間内の個数が出せます。

さらに \(i \ne j\) 条件のため、\(C_i > S_i\) のときは必ず自分自身（\(S_i\)）が区間内に含まれるので、最後に \(1\) 人分引けばよいです。

アルゴリズム

1. 全員のレーティング配列 \(S\) を用意し、それをソートした配列 sortedS を作る。
2. 各メンバー \(i\) について次を行う：
   • もし \(C_i \le S_i\) なら、区間 \([S_i, C_i)\) は空（または不適）なので 0 人としてスキップ。
   • そうでなければ、二分探索で
     • \(l =\) lower_bound(sortedS, S_i)（\(S_j \ge S_i\) となる最初の添字）
     • \(r =\) lower_bound(sortedS, C_i)（\(S_j \ge C_i\) となる最初の添字） を求める。
   • 区間 \([S_i, C_i)\) に入る人数は \(r-l\)。
   • ただし \(C_i > S_i\) のとき自分自身も必ず数えられているので、\(r-l-1\) を答えに加える。
3. 合計を出力する。

（例）\(S=[3,5,7,7]\)、ある人が \((S_i,C_i)=(5,8)\) のとき
区間は \([5,8)\) なので該当する \(S_j\) は \(5,7,7\) の3人。自分（\(S=5\)）を除いて 2 ペア加算します。

計算量

• 時間計算量: \(O(N\log N)\)（ソート \(O(N\log N)\) ＋ 各人の二分探索 \(O(\log N)\) を \(N\) 回）
• 空間計算量: \(O(N)\)（レーティング配列とソート済み配列）

実装のポイント

• Python では bisect_left が lower_bound と同じ働きをします。

• \(C_i \le S_i\) のときは必ず 0 なので先に continue すると安全で分かりやすいです。

• ans += (r - l) - 1 の -1 は \(i \ne j\) のための「自分自身の除外」です。同じレーティングの他人がいても、引くのは 1 人分だけで正しいです。

  ソースコード

import sys
from bisect import bisect_left

def main():
    input = sys.stdin.readline
    N = int(input())
    S = []
    C = []
    for _ in range(N):
        s, c = map(int, input().split())
        S.append(s)
        C.append(c)

    sortedS = sorted(S)
    ans = 0

    for s, c in zip(S, C):
        if c <= s:
            continue
        l = bisect_left(sortedS, s)   # first index with Sj >= s
        r = bisect_left(sortedS, c)   # first index with Sj >= c (i.e., Sj < c)
        cnt = r - l
        ans += cnt - 1  # exclude j = i (since s < c, i is counted)

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。