2022-03-09 アルゴリズムと数学演習問題集 076, 077 を解いた

アルゴリズムと数学演習問題集 076 - Sum of difference を解いた。

問題: https://atcoder.jp/contests/math-and-algorithm/tasks/abc186_d

ABC186 D https://atcoder.jp/contests/abc186/tasks/abc186_d と同じ問題。愚直に二重ループしてしまうと間に合わない。

各組について差の絶対値を求め、その総和を求めよと書いてある。差の絶対値なので並び順は問題ではなくソートしても構わないことが分かる。また |A_i - A_j| なので A_i >= A_j のときは A_i - A_j で A_i < A_j のときは A_j - A_i になる。 A を昇順にソートしてしまえば常に A_j - A_i になる。ここまでで A_i <= A_j (1 <= i < j <= N) な A で \sum_{i=1}^{N-1}{\sum_{j=i+1}^{N}{A_j-A_i}} を求めれば良いと分かる。

ここまで整理すればあとは 074 - Sum of difference Easy (2022-03-07) と同じ問題になっている。 \sum_{i=1}^N (i-1)A_i-(N-i)A_i なので O(N) となり間に合う。

提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29963634 解説: https://atcoder.jp/contests/abc186/editorial/402

アルゴリズムと数学演習問題集 077 - Distance Sum を解いた。

問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bj

各組について距離を求め、その総和を求める。

\sum_{i=1}^{N}{\sum_{j=i+1}^{N}{dist(i,j)}}

まず dist を展開する。距離の計算がマンハッタン距離 (|x_1-x_2|+|y_1-y_2|) である。

\sum_{i=1}^{N}{\sum_{j=i+1}^{N}{|x_i-x_j|+|y_i-y_j|}}

次に \sum を x に関するものと y に関するもののふたつに分ける。

\sum_{i=1}^{N}{\sum_{j=i+1}^{N}{|x_i-x_j|}}+\sum_{i=1}^{N}{\sum_{j=i+1}^{N}{|y_i-y_j|}}

ここまで整理すればあとは 076 - Sum of difference (2022-03-09) と同じ問題だ。

提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29973181

育児。上の子は「ちゅーちゅー (おそらくディズニーツムツムのぬいぐるみ) 」がお気に入りだ。いつも持ち歩いて一緒に寝ている。

今日のコミット。