概要

同じ競技にエントリーしていて、かつ異なるチームに所属する2人の選手の組み合わせ数を求める問題です。「同じ競技のペア数」から「同じ競技かつ同じチームのペア数」を引く、という補集合の考え方で効率的に解けます。

考察

素朴なアプローチの問題点

最も単純な方法は、\(N\) 人の選手からすべての2人組 \(\frac{N(N-1)}{2}\) 通りを列挙し、各ペアについて「同じ競技か？」「異なるチームか？」を判定することです。しかし、\(N\) が最大 \(2 \times 10^5\) のため、ペア数は最大約 \(2 \times 10^{10}\) 通りとなり、TLE（時間超過）になります。

重要な気づき：補集合で考える

対戦が成立する条件は「同じ競技 かつ 異なるチーム」です。これを直接数えるのは難しいので、次のように分解します。

\[\text{対戦成立ペア数} = \text{同じ競技のペア数} - \text{同じ競技かつ同じチームのペア数}\]

つまり、まず同じ競技に属するペアをすべて数え、そこから同じチーム同士のペア（対戦できない）を引けばよいのです。

具体例

例えば、競技1に5人いるとします。この5人から2人を選ぶペア数は \(\binom{5}{2} = 10\) 通りです。

そのうち、競技1でチームAに3人、チームBに2人いるなら、同じチームのペア数は \(\binom{3}{2} + \binom{2}{2} = 3 + 1 = 4\) 通りです。

よって、競技1で対戦が成立するペア数は \(10 - 4 = 6\) 通りです。

アルゴリズム

1. 競技ごとの人数を数える: sport_count[p] に、競技番号 \(p\) にエントリーしている選手数を格納します。
2. （競技, チーム）ごとの人数を数える: sport_team_count[(p, q)] に、競技 \(p\) かつチーム \(q\) に属する選手数を格納します。
3. 同じ競技のペア数を合計する: 各競技について \(\binom{n}{2} = \frac{n(n-1)}{2}\) を計算し、合計します。
4. 同じ競技かつ同じチームのペア数を引く: 各（競技, チーム）の組について \(\binom{c}{2} = \frac{c(c-1)}{2}\) を計算し、合計から引きます。

最終的な値が答えです。

計算量

• 時間計算量: \(O(N)\) — 各選手を1回ずつ処理し、Counter の各エントリを1回ずつ走査するだけです。
• 空間計算量: \(O(N)\) — Counter に格納するエントリ数は最大 \(N\) 個です。

実装のポイント

• Counter（辞書）を活用: Pythonの collections.Counter を使うことで、競技ごと・（競技, チーム）ごとの人数集計を簡潔に書けます。

• 組み合わせ数の公式: \(n\) 人から2人を選ぶ組み合わせ数 \(\binom{n}{2} = \frac{n(n-1)}{2}\) は頻出公式です。整数除算 // を使って正確に計算できます。

• 引き算で求める発想: 「条件Aかつ条件B」を直接数えるのが難しい場合、「条件Aの全体」から「条件Aかつ条件Bでない部分」を引くテクニックは競技プログラミングで非常によく使います。

  ソースコード

from collections import Counter

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    players = []
    for _ in range(N):
        p, q = map(int, input().split())
        players.append((p, q))
    
    # Count players per sport
    sport_count = Counter()
    # Count players per (sport, team) pair
    sport_team_count = Counter()
    
    for p, q in players:
        sport_count[p] += 1
        sport_team_count[(p, q)] += 1
    
    # For each sport, total pairs = C(n, 2)
    # Same-team pairs in that sport = sum of C(c, 2) for each team
    # Valid pairs = total pairs - same-team pairs
    
    answer = 0
    for sport, n in sport_count.items():
        answer += n * (n - 1) // 2
    
    for (sport, team), c in sport_team_count.items():
        answer -= c * (c - 1) // 2
    
    print(answer)

main()

---

この解説は claude4.6opus-thinking によって生成されました。