ABC194 C - Squared Error에서 배운

흠흠. 샘플을 보자.



흠. 시그마를 사용하고 있지만 결국,
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 로 시험해 주었으면 한다.
필기로 전부 열거해 계산하면 놀라움이 기다리고 있다.