Python3で解く AtCoder Beginner Contest 186 D - Sum of difference

結構単純な、数え上げ。ソートして考えることにきづければ簡単。

概要

問題

問題概要は省略。

解くときに考えた内容

すべてのパターンは $\frac{(n)\times (n-1)}{2}$ でも制約的に、線形で考えなくてはいけないので二重のforではだめ。
差の絶対値をとったものの和なので順番をソートしても問題ない。
大きい順にする。
あとはindexと対応する値を適切に足し合わせたり、引いたりする。
- 簡易的な例を考えると、 $A = [2, 3, 5, 1, 4]$ だとした時に、順番に引き算すると $|2-3|, |2-5|, |2-1|, |2-4| ... |5-1|, |5-4|, |1-4|$ となる。図を見ると、大きい順にソートしてから考えた時と、計算結果は変わらないことがわかる。（左右が入れ替わったパターンが出てくるだけでそれは絶対値によって和にするならば一致するため）
- ここまで理解できれば、あとは規則性。
- 全体でどれがどれだけ+なのか-なのかを考える。
- $5$ が $4$ 回加算される（図では+） $0$ 回減算される（図では-）。
- $4$ が $3$ 回加算される（図では+） $1$ 回減算される（図では-）。
- 一般に $sorted_A[index]$ が $n-index -1$ 回加算される（図では+） $index$ 回減算される（図では-）。

f:id:black_tank_top:20201220003525j:plain — パターンのイメージ図

最近は実際のコンテストの最中にイメージ図を書くようにしている。その方が、indexとの関係などをが明白になってミスが減っている気がしている。上の図も実際の場面で書いたもの。

コード

n = int(input())
A = sorted([int(x) for x in input().split()], reverse=True)
ans = 0
for i in range(n):
    ans += A[i] * ((n-i-1) - i)
print(ans)

参考になる書籍

問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

とうとう発売され自分の手元にも来た（2020-10-03）。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う（答え合わせできるのはありがたい）。