【ABC186 D】「Sum of difference」を解く【Python3】

コンテスト一覧へ

 

N個の整数Aiに対して、1≦ i < j ≦N を満たす、すべてのi, j の組について |Ai – Aj| の和を求める問題です。

提出
n = int(input())
a = list(map(int, input().split()))

a.sort()
s = a[0]
ans = 0

for i in range(1,n):
    ans += a[i]*i-s
    s += a[i]

print(ans)

すべての組み合わせを計算していては時間が間に合わないので、工夫して計算する必要があります。

Ai はリストにしておきます。

答えは、すべての組み合わせの和であるので、このリストをソートしても問題ありません。

入力例1の場合、ソートした後は、

a = [1, 2, 5]

となります。最初の1では何もせず、次の2で「2-1」を行い、次の5で「5-2」「5-1」をすると考えます。

a = [1, 2, 5] の要素をそれぞれ a[0], a[1], a[2] とすると、「5-2」「5-1」は合わせて、

a[2]×2 - (a[1]+a[2])

と書くことができます。もし、続きのa[3], a[4] があれば、

a[3]×3 - (a[1]+a[2]+a[3])
a[3]×4 - (a[1]+a[2]+a[3]+a[4])

を足していくことで答えを求められます。

ということで、右側の「a[1]+a[2]+……」の部分を「s」として、その都度足していきます。

最後に ans を出力します。

【ABC186】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。