Edit

【pythonでABC194を解説】C - Squared Error

問題概要

問題ページ

C - Squared Error
C - Squared Error

問題ページへ移動する

問題文

長さ \(N\) の数列 \(A\) が与えられます。
各要素同士の差の \(2\) 乗の和、すなわち \(\displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2\) を求めてください。

制約

  • \(2 \le N \le 3 \times 10^5\)
  • \(|A_i| \le 200\)
  • 入力に含まれる値は全て整数

問題の考察

ACコード

import sys


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


if __name__ == '__main__':
    solve()

-Edit
-