ABC186D
from ABC186
ABC186D
Twitter上では累積和を使うという話が多いですが僕は累積和を使ってません。
ソートして隣接した項の差をとったものをDiとするなら解の中のDiの出現回数はi(N-i)なので掛けて足すだけ。
S = \sum_{i=1}^{N-1} D_i i (N - i) = \sum_{i=0}^{N-2} D_i (i+1)(N-i-1)
pythondef 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)ところでTwitterを見てたら「なんでソートしていいの？」という投稿があった
求める値はN個の値から2つを取り出すすべての組み合わせに対して、2つの数の順序によらない数を足し合わせてる
対称性から順序をどのように入れ替えても結果が変わらない
だから扱いやすい「ソートされてるもの」にした
Related Pages
- →僕のatcoderの学び方(〜水色)×僕のatcoderの学び方(〜past上級)×abc187×past過去問練習202012×変形テクニックに名前をつける×頂点数18の制約×辺が10^5の制約×行列の半分×二項定理×足し算の順序の変更×辺が10^5ならダイクストラ使える×典型力×問題変換×問題分割×認知の解像度×概念のハンドル×atcoder失敗リスト×atcoderentrypoint×アルゴリズム実技検定×第五回_アルゴリズム実技検定×最小費用流に帰着×帰着訓練→
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×ARC106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×unionfind×mod_pでの組み合わせ×educational_dp_contest×動的計画法×atcoder_library_practice_contest×atcoder_library×帰着する力×帰着訓練→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]