アルゴリズムと数学 演習問題集 074 - Sum of difference Easy を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bh
例題。愚直に二重ループしてしまうと O(N^2) で N <= 2 * 10^5 という制約なので間に合わない。何かしらの工夫が必要になる。
試しに N = 4 A = {1, 2, 3, 4} として書き出してみる。
(2 - 1) + (3 - 1) + (4 - 1) + (3 - 2) + (4 - 2) + (4 - 3)
外側のループ・内側のループでグループ化するのではなく出てくる数字に注目して整理する。 1 が足されるのは 0 回で引かれるのは 3 回。 2 は 1 回と 2 回。 3 は 2 回と 1 回。 4 は 3 回と 0 回。つまり A_i が足されるのは i - 1 回で引かれるのは N - i 回になる。 \sum_{i=1}^N (i-1)A_i-(N-i)A_i 。
これで 1..=N の一重のループにできるので O(N) となり間に合う。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29937793
今日のコミット。
