ABC186D

from ABC186 ABC186D

• 
• D - Sum of difference
• There is a lot of talk on Twitter about using cumulative sums, but I don’t use cumulative sums.
• If you sort and take the difference between adjacent terms and let Di be the number of occurrences of Di in the solution is i(N-i), so just multiply and add.
  • 
  • $S={\sum }_{i=1}^{N-1}{D}_{i}i(N-i)={\sum }_{i=0}^{N-2}{D}_i(i+1)(N-i-1)$ python

def main():
    N = int(input())
    AS = list(map(int, input().split()))
    AS.sort()
    DS = []
    for i in range(N - 1):
        DS.append(AS[i + 1] - AS[i])
    ret = 0
    for i in range(N - 1):
        ret += DS[i] * (N - 1 - i) * (i + 1)
    print(ret)

• By the way, I was on Twitter and saw a post that said, “Why should I sort?” There was a post that said

  • The value you’re looking for is adding two unordered numbers for every combination that takes two out of N values.

  • 

  • No matter how you swap the order from symmetry to symmetry, the result remains the same.

  • So I went with “sorted” which is easier to handle.

  • Sort and remove absolute values.

  • Change the order of addition

  • Symmetrical, so you can reorder them.

    • The order is irrelevant.

---

This page is auto-translated from /nishio/ABC186D using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.