AtCoder Beginner Contest 177 [ C - Sum of product of pairs ]をPythonで解く（300点、⬜️灰色diff）

問題

atcoder.jp

解法

制約が N ≤ 2×10⁵なので、普通にシミュレーションするとO(10⁸)超えるのは目に見えてる。
なので、計算量を減らす工夫をする必要があるんだけど、これは解法みないとわからなかったー。

数列A = { 3, 1, 4 }
とする。
答えは 3 x 1 + 3 x 4 + 1 x 4 = 19

ABC177C

要素ごとの積をマトリクスにすると、こんな図になる。
下の三角部分の合計が答え。

ABC177C_2

このマトリクスの各辺の長さをAの値を反映させると見た目がわかりやすくなる。
全体の面積は、Aの合計 x Aの合計。
あとは対角線部分の値を引いて、２で割れば答えが出る。

この計算量減らす方法は、知らんかったなー。
なるほどね。

実装

参考

youtu.be