概要

同じ学校に所属する選手のペアすべてについて、ゴールタイムの差の絶対値を計算し、その総和を求める問題です。

考察

素朴なアプローチ

最も単純な方法は、同じ学校の選手のすべてのペア \((i, j)\) について \(|L_i - L_j|\) を計算することです。

# 素朴な方法（イメージ）
for i in range(n):
    for j in range(i+1, n):
        total += abs(times[i] - times[j])

この方法だと、1つの学校に \(n\) 人いる場合、ペア数は \(\frac{n(n-1)}{2}\) 個となり、\(O(n^2)\) の計算量がかかります。今回の制約 \(N \leq 1000\) では問題ありませんが、より効率的な方法を学んでおくと良いでしょう。

重要な気づき：ソートを利用する

タイムをソートすると、絶対値を外すことができます。

例えば、タイムが \([2, 5, 9]\) の場合（ソート済み）： - \(5\) は \(2\) より大きいので、\(|5-2| = 5-2\) - \(9\) は \(2, 5\) より大きいので、\(|9-2| = 9-2\)、\(|9-5| = 9-5\)

つまり、ソート済み配列において、\(times[i]\) は自分より小さい \(i\) 個の要素すべてとの差に「正の側」として寄与します。

数式で整理

ソート済み配列 \(times[0], times[1], \ldots, times[n-1]\) において、\(times[i]\) が寄与する差の合計は：

\[\sum_{j=0}^{i-1} (times[i] - times[j]) = times[i] \times i - \sum_{j=0}^{i-1} times[j]\]

右辺の \(\sum_{j=0}^{i-1} times[j]\) は累積和（prefix sum）として事前に計算できます。

具体例

タイム \([2, 5, 9]\) の場合： - \(i=0\): 寄与 = \(2 \times 0 - 0 = 0\) - \(i=1\): 寄与 = \(5 \times 1 - 2 = 3\)（\(|5-2|=3\) に対応） - \(i=2\): 寄与 = \(9 \times 2 - (2+5) = 18 - 7 = 11\)（\(|9-2|+|9-5|=7+4=11\) に対応）

総和 = \(0 + 3 + 11 = 14\) ✓

アルゴリズム

1. 学校ごとにグループ化: 各選手のタイムを所属学校ごとにリストに格納する
2. 各学校について処理:
   • タイムをソートする
   • 累積和を使って、各要素がより小さい要素との差に寄与する分を計算
   • \(times[i] \times i - prefix\_sum\) を総和に加算
   • \(prefix\_sum\) を更新
3. 全学校の総和を出力

計算量

• 時間計算量: \(O(N \log N)\)
  • 学校ごとのソートに \(O(N \log N)\)（全選手を合わせて）
  • 累積和による計算に \(O(N)\)
• 空間計算量: \(O(N)\)
  • 学校ごとのタイムリストの格納に使用

実装のポイント

• defaultdict(list) を使うと、学校番号をキーとして選手のタイムを簡単にグループ化できる

• 累積和 prefix_sum は整数型で管理し、ループの中で更新していく

• ソート後に処理することで、絶対値を考慮する必要がなくなり、計算が単純化される

  ソースコード

from collections import defaultdict

def solve():
    N = int(input())
    
    # 学校ごとに選手のタイムを格納
    school_times = defaultdict(list)
    
    for _ in range(N):
        C, L = map(int, input().split())
        school_times[C].append(L)
    
    total = 0
    
    # 各学校について計算
    for school, times in school_times.items():
        # タイムをソート
        times.sort()
        n = len(times)
        
        # ソート済み配列で効率的に計算
        # i番目の要素は、i個の小さい要素との差に寄与し、(n-1-i)個の大きい要素との差に寄与
        # 総和 = Σ times[i] * i - Σ times[j] (j < i) for all i
        #      = Σ times[i] * i - prefix_sum[i]
        
        prefix_sum = 0
        for i in range(n):
            # times[i]より小さい要素との差の総和
            total += times[i] * i - prefix_sum
            prefix_sum += times[i]
    
    print(total)

solve()

---

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