Edit

【pythonでABC186を解説】D - Sum of difference

問題概要

問題ページ

D - Sum of difference
D - Sum of difference

問題ページへ移動する

問題文

\(N\) 個の整数 \(A_1,\ldots,A_N\) が与えられます。

\(1\leq i < j \leq N\) を満たす全ての \(i,j\) の組についての \(|A_i-A_j|\) の和を求めてください。

すなわち、\(\displaystyle{\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} |A_i-A_j|}\) を求めてください。

制約

  • \(2 \leq N \leq 2 \times 10^5\)
  • \(|A_i|\leq 10^8\)
  • \(A_i\) は整数である。

問題の考察

 

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    a.sort()
    sa = sum(a)
    total = 0
    for i in range(n):
        sa -= a[i]
        total += sa - a[i] * (n - (i + 1))
    print(total)


if __name__ == '__main__':
    solve()

-Edit
-