公式

B - 過信と実力 / Overconfidence and True Ability 解説 by MMNMM


この問題では、事前に全員のレーティングを探索しやすい形にして保持することによって高速に答えを求めることができます。

例えば、レーティングが昇順になるように並べた列を作っておき、「レーティングが \(X\) 以上のメンバーが何人いるか」を二分探索で求められるようにすると、あるメンバー \(i\) が見下しているメンバーの人数は、(\(S _ i\lt C _ i\) なら、)レーティングが \(S _ i\) 以上のメンバーの人数からレーティングが \(C _ i\) 以上のメンバーの人数\({}+1\) を引いたものになります。

よって、これを使うと \(O(N\log N)\) 時間でこの問題を解くことができます。

実装例は以下のようになります。

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

int main() {
    using namespace std;
    int N;
    cin >> N;

    vector<pair<int, int>> member(N);
    for (auto& [S, C] : member) {
        cin >> S >> C;
    }
    ranges::sort(member); // S の昇順にメンバーを並べておく

    long ans = 0;
    for (auto [S, C] : member) {
        if (S < C) { // S < C なら
            // 二分探索で見下しているメンバーの人数を求める
            ans += ranges::lower_bound(member, C, {}, &pair<int, int>::first) - ranges::lower_bound(member, S, {}, &pair<int, int>::first) - 1;
        }
    }
    cout << ans << endl;
    return 0;
}
from bisect import bisect_left


N = int(input())

member = [tuple(map(int, input().split())) for i in range(N)]
member.sort() # S の昇順にメンバーを並べておく

ans = 0
for S, C in member:
    if S < C: # S < C なら
        # 二分探索で見下しているメンバーの人数を求める
        ans += bisect_left(member, (C, 0)) - bisect_left(member, (S, 0)) - 1

print(ans)

投稿日時:
最終更新: