ABC194 C - Squared Error から学んだ

6787 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク

ふむふむ。サンプルを見てみよう

うーん。シグマ使ってるけど、結局、
A の要素の組み合わせで差 => 二乗 で良くね？

だがしかし、WA

SquaredError_r0.py
N = int(input())
A = list(map(int,input().split()))

#辞書で要素をリスト 
dic = {} 
for i in range(N):
    if A[i] not in dic:
        dic[A[i]] = 0
    dic[A[i]] += 1

#配列長の N でカウントすると 3*10^5 もあるので
#条件の|A|<200 を使って combination すれば良いかと。
score = 0
from itertools import combinations
for a,b in combinations(range(-200,201),2):
    if a in dic and b in dic:
        score += (a-b)**2
print(score)

結局、条件には A の要素は全て異なる値とは書いていない。
もしかして重複する可能性もあるのか？
解説を聞いたが、自分の力不足なのか、ピンとこない。

有識者の解答を見るとしっくり来るものを見つけた。
結局、重複したことを前提に書き換えると良いみたいだ。

SquaredError_r1.py
N = int(input())
A = list(map(int,input().split()))

dic = {}

for i in range(N):
    if A[i] not in dic:
        dic[A[i]] = 0
    dic[A[i]] += 1
score = 0
from itertools import combinations
for a,b in combinations(range(-200,201),2):
    if a in dic and b in dic:
        score += dic[a]*dic[b]*(a-b)**2# <= dic[a], dic[b] の値を掛けた。
print(score)

試しに 1,2,2,1 or 1,2,3,1 で試してほしい。
手書きで全部列挙して計算すると驚きが待っている。