アルゴリズムと数学 演習問題集 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
育児。上の子は「ちゅーちゅー (おそらくディズニーツムツムのぬいぐるみ) 」がお気に入りだ。いつも持ち歩いて一緒に寝ている。
今日のコミット。
