概要

同じ学校に所属する選手のペアごとにタイム差の絶対値を求め、その総和を出力する問題です。

考察

この問題では、同じ学校に所属する選手同士のペアすべてについて、タイム差の絶対値の和を求める必要があります。

素朴な方法とその問題点

まず思いつくのは、全ペアに対して差の絶対値を計算する方法です。つまり、同じ学校の選手が \(k\) 人いるとき、\({}_kC_2 = \frac{k(k-1)}{2}\) 個のペアについて、それぞれ \(|L_i - L_j|\) を求めます。しかし、最悪の場合、ある学校に \(N\) 人が所属しているとすると、この計算は最大 \(O(N^2)\) 回の比較が必要になり、全体では \(O(N^2)\) の時間計算量になります。制約が \(N \leq 1000\) なので、十分高速ではありませんが、Pythonなどで実装すると間に合わない可能性があります。

効率的な方法への気づき

そこで、タイムをソートして考えることで、効率的に計算できないかを考えます。タイムを昇順にソートした配列を \([t_0, t_1, ..., t_{k-1}]\) とします。

ここで注目するのは、各要素 \(t_i\) が他の要素とどれだけ寄与するかです。

• \(t_i\) より前の要素（\(t_0\) 〜 \(t_{i-1}\)）とは、\(t_i > t_j\ (j < i)\) なので、差は \(t_i - t_j\)
• \(t_i\) より後の要素（\(t_{i+1}\) 〜 \(t_{k-1}\)）とは、\(t_i < t_j\ (j > i)\) なので、差は \(t_j - t_i\)

したがって、\(t_i\) が全体に与える寄与は： $\( \sum_{j=0}^{i-1}(t_i - t_j) + \sum_{j=i+1}^{k-1}(t_j - t_i) = t_i \cdot i - \sum_{j=0}^{i-1}t_j + \sum_{j=i+1}^{k-1}t_j - t_i \cdot (k-1-i) \)$

これを整理すると： $\( t_i \cdot (2i - k + 1) + \left(\sum_{j=i+1}^{k-1}t_j - \sum_{j=0}^{i-1}t_j\right) \)$

しかし、累積和を使えばもっと簡単に、各 \(t_i\) の係数として \(2i - k + 1\) を直接求められます。

つまり、各タイムリストをソートした後、各要素に対し、その係数 \((2i - k + 1)\) を使って線形で合計を計算できます。

これにより、各学校ごとの計算が \(O(k)\) で済み、全体でも \(O(N)\) で処理可能です。

アルゴリズム

1. 各学校に所属する選手のタイムを defaultdict を用いてリストに分類します。
2. 各学校ごとにタイムをソートします。
3. 各タイムリストについて、以下のように計算します：
   • タイムをソートしたリストを \([t_0, t_1, ..., t_{k-1}]\) とする。
   • 各 \(i\) について、\(t_i \cdot (2i - k + 1)\) を合計に加算します。
4. 最終的な合計を出力します。

計算量

• 時間計算量: \(O(N \log N)\)（各学校のタイムをソートする必要があるため）
• 空間計算量: \(O(N)\)（選手情報を保存するため）

実装のポイント

• defaultdict(list) を使うことで、学校ごとにタイムを効率的に格納できます。
• 各学校のタイムは必ずソートしてから計算を行う必要があります。
• 差の絶対値の和を直接計算せず、ソートと係数計算を使うことで効率化しています。

## ソースコード

```python
from collections import defaultdict

N = int(input())
schools = defaultdict(list)

for _ in range(N):
    C, L = map(int, input().split())
    schools[C].append(L)

total_sum = 0

for times in schools.values():
    times.sort()
    k = len(times)
    for i in range(k):
        total_sum += times[i] * (2 * i - k + 1)

print(total_sum)

---

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