概要

本問題は、与えられた条件「\(S_i \leq S_j < C_i\) かつ \(i \neq j\)」を満たすペア \((i, j)\) の総数を、高速に数え上げる問題です。

考察

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

すべてのペア \((i, j)\) について条件を満たすかを愚直に判定する場合、ループが二重になり \(O(N^2)\) の計算量がかかります。 本問題では \(N \le 2 \times 10^5\) であるため、最悪の場合に約 \(4 \times 10^{10}\) 回の計算が必要となり、実行時間制限に間に合わず TLE（実行時間制限超過） となってしまいます。したがって、より高速なアプローチが必要です。

条件の整理と高速化のアイデア

メンバー \(i\) を主役に固定して、条件を満たす相手 \(j\) が何人いるかを高速に数え上げることを考えます。 メンバー \(i\) がメンバー \(j\) を見下している条件は、以下の通りです。 1. \(i \neq j\) 2. \(S_i \leq S_j < C_i\)

ここで、各 \(i\) について \(S_i\) と \(C_i\) の大小関係で場合分けをします。

• \(C_i \le S_i\) のとき \(S_i \le S_j < C_i\) を満たす \(S_j\) は存在しません（下限が上限以上になるため）。よって、このメンバー \(i\) が見下している相手は \(0\) 人です。

• \(C_i > S_i\) のとき \(S_i \le S_j < C_i\) を満たす \(j\) を探します。 この範囲には、自分自身（\(j = i\)）が必ず含まれます（\(S_i \le S_i < C_i\) が成り立つため）。 しかし、条件 \(i \neq j\) より自分自身は除外しなければなりません。 したがって、全メンバーのレーティングの中から \(S_i \le S_j < C_i\) を満たすものの個数を求め、そこから 自分自身の分として \(1\) を引いた値 が、メンバー \(i\) が見下している相手の数になります。

「ある範囲（\(S_i\) 以上 \(C_i\) 未満）に存在する要素の個数」は、レーティングの配列をソートしておくことで、二分探索を用いて高速に求めることができます。

アルゴリズム

1. すべてのメンバーのレーティング \(S\) を昇順にソートした配列 \(A\) を作成します。
2. 答えを格納する変数 ans を \(0\) で初期化します。
3. 各メンバー \(i\) (\(1 \le i \le N\)) について、以下を順に行います。
   • \(C_i > S_i\) である場合のみ、以下の処理を行います。
   • 配列 \(A\) において、値が \(C_i\) 未満である要素の個数を二分探索（bisect_left）で求めます。これを \(R\) とします。
   • 配列 \(A\) において、値が \(S_i\) 未満である要素の個数を二分探索で求めます。これを \(L\) とします。
   • 半開区間 \([S_i, C_i)\) に含まれるレーティングの個数は \(R - L\) 個となります。
   • 自分自身を引いた値 \(R - L - 1\) を ans に加算します。
4. 最終的な ans の値を出力します。

具体例での説明

\(S = [2, 5, 12]\), \(C = [10, 3, 15]\) とします。ソート済みの配列は \(A = [2, 5, 12]\) です。

• メンバー 1 (\(S_1=2, C_1=10\)) : \(C_1 > S_1\) なので探索します。
  • \(10\) 未満の要素数は \(2\) 個（\(2, 5\)） \(\to R = 2\)
  • \(2\) 未満の要素数は \(0\) 個 \(\to L = 0\)
  • \(R - L - 1 = 2 - 0 - 1 = 1\) 人（メンバー 2 を見下している）
• メンバー 2 (\(S_2=5, C_2=3\)) : \(C_2 \le S_2\) なのでスキップします（\(0\) 人）。
• メンバー 3 (\(S_3=12, C_3=15\)) : \(C_3 > S_3\) なので探索します。
  • \(15\) 未満の要素数は \(3\) 個（\(2, 5, 12\)） \(\to R = 3\)
  • \(12\) 未満の要素数は \(2\) 個（\(2, 5\)） \(\to L = 2\)
  • \(R - L - 1 = 3 - 2 - 1 = 0\) 人。

合計で \(1 + 0 + 0 = 1\) ペアとなります。

計算量

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

  • レーティング配列 \(S\) のソートに \(O(N \log N)\) かかります。
  • 各メンバーに対する二分探索（bisect_left）は \(O(\log N)\) であり、これを \(N\) 回行うため全体で \(O(N \log N)\) となります。
  • \(N = 2 \times 10^5\) のとき、\(N \log N \approx 3.6 \times 10^6\) 回の計算となり、実行時間制限（通常 2 秒）に十分間に合います。

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

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

実装のポイント

• 自分自身の除外: \(C_i > S_i\) のとき、二分探索で求めた件数には必ず自分自身（\(S_i\)）が含まれるため、最後に必ず 1 を引く必要があります。この処理を忘れると、自分自身を見下している（自己矛盾した）カウントが含まれてしまい、WA（不正解）になります。

• 二分探索のライブラリ: Python では bisect モジュールの bisect_left を使用することで、指定した値未満の要素数を \(O(\log N)\) で簡潔に取得できます。

  ソースコード

import sys
from bisect import bisect_left

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    
    S = [0] * N
    C = [0] * N
    for i in range(N):
        S[i] = int(data[2 * i + 1])
        C[i] = int(data[2 * i + 2])
    
    A = sorted(S)
    
    ans = 0
    for i in range(N):
        si = S[i]
        ci = C[i]
        if ci > si:
            idx_S = bisect_left(A, si)
            idx_C = bisect_left(A, ci)
            ans += idx_C - idx_S - 1
            
    print(ans)

if __name__ == '__main__':
    solve()

---

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