【ABC194 C】「Squared Error」を解く【Python3】

「AtCoder」解説一覧へ

与えられた数列Aの各要素同士の差の2乗の和を求める問題です。

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

ans = (n-1)*a[0]**2
b = a[0]

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

print(ans)

2≦N≦3×10⁵ なので、 (A_i – A_j)² の計算を愚直にする方法では間に合いません。

そこで、

(A_i – A_j)² = A_i² – 2A_iA_j + A_j²

となることを利用して計算します。

問題文から、i > j となる (A_i – A_j)² を求めればいいことが分かります。

for文を用いて、それぞれのA_iに対して、(N-1)×A_i²、2×A_i×b を求めます。

b は、それまでのA_iの総和です。

A₂ のときは、2×A₂×(A₁)、A₃ のときは、2×A₃×(A₁+A₂)となります。

これらを「ans」に加えていき、最後に「ans」を出力します。

【ABC194】解説記事リスト

【ABC194 A】「I Scream」を解く【Python3】

【ABC194 B】「Job Assignment」を解く【Python3】

【ABC194 C】「Squared Error」を解く【Python3】

「AtCoder」解説一覧に戻る