ABC 194C-Squard Error의 기록

본공연 때 풀지 못했는데 차를 우려내려고 고쳤어요.
파이톤으로 구현합니다.공식 해설의 해법 1에서 실현되다.
https://atcoder.jp/contests/abc194/tasks/abc194_c

문제 개요


길이 N의 수열 A 각 요소의 차이의 제곱의 합을 구하다.
\sum^N_{i=2}\sum^{i-1}_j (A_i -A_j)^2

해법


나쁜 조합의 종류는 400^2=1.6\times10^5 정도로 해결할 수 있습니다.
  • 우선, -200부터 200까지의 숫자는 각각 몇 개, 수열 An에 포함된 횟수(출현 횟수)를 계산하는 디렉터리를 생성합니다.
  • 이어서 화해를 구한다.i=-200\sim200, j=i+1\sim200에 대해 각각
    (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)  # 整数型にするため // で割っている
    

    참고 자료


    https://blog.hamayanhamayan.com/entry/2021/03/07/000632
    https://note.com/taraba_kanico/n/n8aca58bcd303

    좋은 웹페이지 즐겨찾기