ABC 194C-Squard Error의 기록
파이톤으로 구현합니다.공식 해설의 해법 1에서 실현되다.
문제 개요
길이 N의 수열 A 각 요소의 차이의 제곱의 합을 구하다.
\sum^N_{i=2}\sum^{i-1}_j (A_i -A_j)^2
해법
나쁜 조합의 종류는 400^2=1.6\times10^5 정도로 해결할 수 있습니다.
(i-j)^2\times(i의 출현 횟수)\times(j의 출현 횟수)
n = int(input())
a = input().split()
dic = {}
for i in range(-200, 201):
dic[i] = a.count(str(i))
# 和を取る処理
ans = 0
for i in dic.keys(): # このdic.keys() は range(-200,201)で置き換えてもok
for j in range(i + 1, 201):
ans += dic[i] * dic[j] * (i - j) ** 2
print(ans)
참고로 인화 처리가 i, j=-200\ism 200으로 설정되면 TLE가 시간을 초과하여 풀 수 없습니다.# 和を取る処理 i,jの範囲を-200~200でとり、最後に2で割る
ans = 0
for i in dic.keys(): # このdic.keys() は range(-200,201)で置き換えてもok
for j in dic.keys():
ans += dic[i] * dic[j] * (i - j) ** 2
print(ans // 2) # 整数型にするため // で割っている
참고 자료
Reference
이 문제에 관하여(ABC 194C-Squard Error의 기록), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://zenn.dev/damedesu/articles/19d999f5a8daf9텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)