概要

学校ごとに選手のゴールタイムを集め、同じ学校内の全ペア \((i, j)\) について \(|L_i - L_j|\) を足し上げた総和を求めます。

考察

同じ学校に所属する人数を \(k\) とすると、その学校内のペア数は \(\frac{k(k-1)}{2}\) 個あります。素朴に各学校で全ペアを列挙して差の絶対値を足すと、最悪で \(N=1000\) のとき \(O(N^2)\)（約50万回）なので一見間に合いそうですが、一般には人数が増えるとすぐに厳しくなりますし、より良い方法が必要です。

重要な気づきは次の2点です。

• 絶対値の和は「ソート」すると扱いやすい
  ある学校のタイム列を昇順に \(a_0 \le a_1 \le \dots \le a_{k-1}\) とすると、\(i<j\) では \(|a_i-a_j|=a_j-a_i\) になり、絶対値が外れます。
• 各要素の「前にある要素との貢献」を累積和で高速に計算できる
  \(a_j\) が作る差の和は $\( \sum_{i=0}^{j-1} (a_j - a_i) = j\cdot a_j - \sum_{i=0}^{j-1} a_i \)\( となり、\)\sum_{i=0}^{j-1} a_i\( を累積和で持っておけば \)O(1)$ で求まります。

例えばタイムが \([2,5,9]\) のとき（すでにソート済み）、 - \(j=0\): 貢献 \(0\) - \(j=1\): \(1\cdot5-(2)=3\) - \(j=2\): \(2\cdot9-(2+5)=18-7=11\) 合計 \(3+11=14\) で、\(|2-5|+|2-9|+|5-9|=14\) と一致します。

この計算を学校ごとに行い、全学校分を合計すれば答えになります。

アルゴリズム

1. 入力を読み、学校番号 \(C_i\) ごとにタイム \(L_i\) を配列としてまとめる（辞書 groups を使う）。
2. 各学校について以下を行う：
   1. タイム配列 times を昇順ソートする。
   2. 累積和 pref を \(0\) で初期化する。
   3. times を左から順に見て、インデックスを \(i\)、値を \(x\) とするとき
      • 答えに \(x \cdot i - \text{pref}\) を加える（\(x\) とそれ以前の要素との差の総和）。
      • pref += x として累積和を更新する。
3. 全学校の貢献を合計した値を出力する。

計算量

• 時間計算量: \(O\!\left(N \log N\right)\)（学校ごとにソートするが、全体で見れば要素数の合計は \(N\) なので総ソートコストは高々この程度）
• 空間計算量: \(O(N)\)（学校ごとにタイムを保持するため）

実装のポイント

• 学校ごとのグルーピングは dict（setdefault）で簡潔に書けます。

• 差の総和は大きくなり得るので、言語によっては 64bit 整数を使う必要があります（Python は自動で大きい整数を扱えます）。

• ソート後に ans += x * i - pref とする形にすると、二重ループを避けて高速に計算できます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    groups = {}
    for _ in range(N):
        c, l = map(int, input().split())
        groups.setdefault(c, []).append(l)

    ans = 0
    for times in groups.values():
        times.sort()
        pref = 0
        for i, x in enumerate(times):
            ans += x * i - pref
            pref += x

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。