ABC-353

A

解法

---

B

解法

---

C

$URL\:\to$ https://atcoder.jp/contests/abc353/tasks/abc353_c

#尺取り法 #数学

    n = Integer().content
    a = sorted(IntegerList().content)

    sum, count, guard = 0, 0, n
    for i in range(n): sum += (n-1)*a[i]
    for i in range(n):
        guard = max(guard, i+1)
        while i<guard-1 and a[i]+a[guard-1]>=100000000: guard-=1
        count+=n-guard
    print(sum-(count*100000000))

解法

まず $\sum\limits_{i=1}^{N-1} \sum\limits_{j=i+1}^{N} (A_{i}\:+\:A_{j})\: = \: (N-1)\sum\limits_{i=1}^{N}A_{i}$ という風に次数を下げることができます。

$1 \le i \le 5$ のとき $\\[5mm]$ $A_{1}\:+\:(A_{2},\:...,\:A_{5})$ $A_{2}\:+\:(A_{3},\:...,\:A_{5})$ $A_{3}\:+\:(A_{4},\:...,\:A_{5})$ $A_{4}\:+\:(A_{5})$ $\\[5mm]$ $\therefore\:A_{1}:\:4項,\;A_{2}:\:4項,\;A_{3}:\:4項,\;A_{4}:\:4項,\;A_{5}:\:4項$ となり、 それぞれ $(N-1)$ 項出てくることがわかる。

その後、$A_{i}\:+\:A_{j}\:\ge\:10^8$ となる $j$ を尺取り法で求めることで解を求めることができます。

---

D

解法

---

E

解法

---