2022-03-07 アルゴリズムと数学演習問題集 074 - Sum of difference Easy を解いた

アルゴリズムと数学演習問題集 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

今日のコミット。