概要

同じ競技にエントリーしていて、かつ異なるチームに所属する2人の選手の組み合わせの総数を求める問題です。

考察

素朴なアプローチでは、全ての選手の組み合わせ（\(O(N^2)\)通り）をチェックすることになりますが、\(N\)が最大\(2 \times 10^5\)であるため、この方法では時間制限に間に合いません。

重要な観察として、対戦が成立するのは同じ競技内でのみであり、かつ同じチーム同士では対戦できないという点があります。したがって、競技ごとに選手をグループ分けし、各競技内で異なるチームの選手の組み合わせ数を効率的に計算する必要があります。

アルゴリズム

1. 競技番号ごとに選手をグループ化する
2. 各競技について：
   • 競技内の全選手数\(T\)から得られる組み合わせ総数は\(\frac{T(T-1)}{2}\)通り
   • 同じチーム内の組み合わせ数\(\sum_{各チーム} \frac{c_i(c_i-1)}{2}\)を引く
   • これにより、競技内の異なるチーム間の組み合わせ数が得られる
3. 全ての競技について上記の値を合計する

このアプローチでは、競技ごとにチーム分布を保持するために辞書の辞書（defaultdict(lambda: defaultdict(int))）を使用しています。

計算量

• 時間計算量: \(O(N)\)
  • 選手データの読み込みとグループ化に\(O(N)\)
  • 各競技の処理は競技数とチーム数に比例するが、合計で\(O(N)\)
• 空間計算量: \(O(N)\)
  • 選手データの保存とグループ化に必要なメモリ

実装のポイント

• defaultdictをネストして使用することで、競技番号とチーム番号の二次元集計を効率的に行えます

• 各競技内で、全組み合わせ数から同じチーム内の組み合わせ数を引くことで、異なるチーム間の組み合わせ数を求めます

• 整数演算ではオーバーフローに注意（Pythonでは整数は任意精度ですが、大きな数値になる可能性があります）

  ソースコード

import sys
from collections import defaultdict

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    
    players = []
    for i in range(n):
        p = int(data[1 + 2*i])
        q = int(data[2 + 2*i])
        players.append((p, q))
    
    comp_team_count = defaultdict(lambda: defaultdict(int))
    
    for p, q in players:
        comp_team_count[p][q] += 1
    
    total = 0
    for comp in comp_team_count:
        teams = comp_team_count[comp]
        total_players_in_comp = sum(teams.values())
        same_team_pairs = 0
        for count in teams.values():
            same_team_pairs += count * (count - 1) // 2
        
        total += total_players_in_comp * (total_players_in_comp - 1) // 2 - same_team_pairs
    
    print(total)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。