概要

同じ競技に参加している選手同士の組み合わせのうち、「チームが異なる」ペアの数を数えます。競技ごとの総ペア数から、同一チーム内ペア数を引くことで求めます。

考察

対戦が成立する条件は「競技番号が同じ」かつ「チーム番号が異なる」です。

素朴に全ペア \(\frac{N(N-1)}{2}\) を調べると、\(N \le 2\times 10^5\) なので最大で約 \(2\times 10^{10}\) 通りになり、到底間に合いません（TLE）。

そこで数え上げを工夫します。ある競技 \(p\) に参加している選手が \(k\) 人いるとき、その競技内で作れるペア総数は \(k \choose 2\) です。しかしこの中には「同じチーム同士」のペア（対戦不可）も混ざっています。

例えば競技 \(p\) において、チーム \(q\) に所属する人数が \(c_{p,q}\) 人なら、そのチーム内でできる（対戦不可の）ペア数は \({c_{p,q} \choose 2}\) です。よって競技 \(p\) で対戦可能なペア数は $\( {k \choose 2} - \sum_q {c_{p,q} \choose 2} \)$ となります。

これを全競技について合計すれば答えです。つまり、 - まず「競技ごとの人数」を数える - 次に「(競技, チーム) ごとの人数」を数える - \(\sum_p {k_p \choose 2}\) を足し、\(\sum_{p,q} {c_{p,q} \choose 2}\) を引く という方針になります。

アルゴリズム

1. 連想配列（辞書）で以下を数える
   
   • sport_cnt[p] = 競技 \(p\) の参加人数 \(k_p\)
     
   • sport_team_cnt[(p,q)] = 競技 \(p\) かつチーム \(q\) の人数 \(c_{p,q}\)
2. 初期値 ans = 0 とし、全競技について ans += k_p (k_p-1)/2 を加算（競技内ペアの総数）。
3. 全ての \((p,q)\) について ans -= c_{p,q} (c_{p,q}-1)/2 を減算（同一チーム内ペア＝対戦不可分を除外）。
4. ans を出力する。

計算量

• 時間計算量: \(O(N)\)（入力を1回走査して数え、辞書の値を合計するだけ）
• 空間計算量: \(O(N)\)（最悪で競技や (競技,チーム) の種類数が \(N\) 程度）

実装のポイント

• 組み合わせ数は \({x \choose 2} = \frac{x(x-1)}{2}\) を整数演算で x*(x-1)//2 と書く。

• \(N\) が大きいので、Pythonでは sys.stdin.buffer.read() でまとめて読み込むと高速です。

• 辞書は defaultdict(int) を使うとカウントが簡潔に書けます。

  ソースコード

import sys
from collections import defaultdict

def main():
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))

    sport_cnt = defaultdict(int)
    sport_team_cnt = defaultdict(int)

    for _ in range(n):
        p = int(next(it))
        q = int(next(it))
        sport_cnt[p] += 1
        sport_team_cnt[(p, q)] += 1

    ans = 0
    for k in sport_cnt.values():
        ans += k * (k - 1) // 2

    for c in sport_team_cnt.values():
        ans -= c * (c - 1) // 2

    print(ans)

if __name__ == "__main__":
    main()

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