AtCoder Beginner Contest 186 D - Sum of difference 【Python】
https://atcoder.jp/contests/abc186/tasks/abc186_d
AtCoder ProblemsのRecommendationで Difficulty: 436、Solve Probability: 48%でした。
解けませんでした。ソートすると絶対値を外れるというのは思いつきませんでした。
その後の累積和を使うなども全く思いつかなかったため勉強になりました。
以下はyoutubeの公式解説
https://www.youtube.com/watch?v=hY2FicqnAcc
の2つの解法をそのまま実装したものです。
累積和を使う解法
N = int(input()) A = list(map(int, input().split())) A = sorted(A) accum_A = [0] for i in range(N): accum_A.append(accum_A[i] + A[i]) ans = 0 for j in range(1, N): ans += A[j] * j - accum_A[j] print(ans)
累積和を使わない解法
N = int(input()) A = list(map(int, input().split())) A = sorted(A) ans = 0 for i in range(N): ans += A[i] * (i - (N - i - 1)) print(ans)