概要

\(N\) 人の選手の競技番号と所属チーム番号が与えられるので、同じ競技にエントリーし、かつ異なるチームに所属するような2人組の数を求めます。

考察

まず、単純にすべての2人組を試すと、組み合わせは最大で \(\frac{N(N-1)}{2}\) 通りあり、\(N\) が最大 \(2 \times 10^5\) なので、これは時間内に計算できません（TLE）。

重要な観察として、「対戦が成立するのは、同じ競技にエントリーしている」かつ「異なるチームに所属している」という条件があります。したがって、競技番号ごとに選手をグループ分けし、各競技内で異なるチーム同士のペア数を数えるのが効率的です。

例えば、ある競技に所属するチームと人数が以下のような場合を考えましょう： - チームA: 2人 - チームB: 3人 - チームC: 1人

このとき、異なるチームから選ぶ組み合わせの数は、 $\( (2 \times 3) + (2 \times 1) + (3 \times 1) = 6 + 2 + 3 = 11 \)$ となります。

このような計算は、すべてのチームの人数の合計を \(S\)、各チームの人数を \(c_i\) としたとき、 $\( \text{組み合わせ数} = \frac{S^2 - \sum c_i^2}{2} \)\( で求めることができます。これは、同じチーム内の組み合わせ（\)c_i^2$）を引いて、順序を無視するために2で割っていると考えられます。

この式を使うことで、各競技について \(O(T)\)（\(T\) はその競技のチーム数）で計算でき、全体でも十分高速です。

アルゴリズム

1. 各選手を「競技番号 → 所属チーム → 人数」の形で集計します。
2. 各競技に対して、その競技に参加しているチームごとの人数リストを得ます。
3. 上記の公式 \(\frac{S^2 - \sum c_i^2}{2}\) を用いて、その競技での有効なペア数を計算します。
4. 全ての競技についてこれを計算し、合計します。

計算量

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

実装のポイント

• 選手の情報を効率よく読み込むために sys.stdin.read を使用しています。
• defaultdict を使うことで、事前にキーの存在を確認せずにカウントできます。
• 各競技ごとにチームの人数を集計し、上記の公式を適用することで効率的に計算を行っています。

## ソースコード

```python
from collections import defaultdict
import sys

input = sys.stdin.read
data = input().split()

N = int(data[0])
players = [(int(data[2*i+1]), int(data[2*i+2])) for i in range(N)]

# 競技ごとに、チームごとの人数をカウント
competition_teams = defaultdict(lambda: defaultdict(int))

for p, q in players:
    competition_teams[p][q] += 1

total_combinations = 0

# 各競技について
for teams in competition_teams.values():
    team_counts = list(teams.values())
    # ある競技での総対戦数 = Σ (count[i] * count[j]) for i < j
    # これは (sum)^2 - sum of squares を使って高速に計算できる
    total = sum(team_counts)
    square_sum = sum(c * c for c in team_counts)
    combinations = (total * total - square_sum) // 2
    total_combinations += combinations

print(total_combinations)

この解説は qwen3-coder-480b によって生成されました。