AtCoder ABC177 C問題

AtCoder ABC177 C問題

累積和を使った問題が出たので解説。

atcoder.jp

目次

• ACしたコード
• 解説
• はてなブログでMathJaxを使う(参考)

ACしたコード

# coding:utf-8
import itertools
n = int(input())
a = list(map(int, input().split()))
cum = [0] + list(itertools.accumulate(a))
# print(cum)
ans = 0
mod = 10**9 + 7

for i in range(n):
    ans += a[i] * cum[i]
    # print(a[i], cum[i])

print(ans % mod)

解説

片っ端からまじめに \( a_i \times a_j \) を全部組み合わせ出して和を求めるのは、
実行時間的にしんどいので、式変換してみる。
例えば、\( n = 3 \) だったとして、元の式を変換した時はこちら。

元の式： \( a_0 \times a_1 + a_0 \times a_2 + a_1 \times a_2 \)
変換後の式： \( a_0(a_1 +a_2 ) + a_1 \times a_2 \)

こんな感じに集約したところで、\( a \) の累積和を思い出してみると、以下の通り。
\( a \)の累積和： \(a_0 \quad a_0+a_1 \quad a_0+a_1+a_2 \)
$a$の累積和の最初に、0をつければ、 \( 0 \quad a_0 \quad a_0+a_1 \quad a_0+a_1+a_2 \) になる。
これと、 \( a \) の要素を使えば、以下の部分で、

# 抜粋
for i in range(n):
    ans += a[i] * cum[i]
    # print(a[i], cum[i])

上記の部分で、それぞれ \( a \) の要素と \( a \) の累積和(ただし最後の項は不要。 \( a_i \times a_i \) が出てくる)
をかけ合わせることによって \( a_i \times a_j \) を素早く求めることができる。

はてなブログでMathJaxを使う(参考)

今回、MathJaxを入れて、数式もmdの中で書けるようにしてみた。
手書きしたり数式エディタからスクショしたりしてたけど、これは超便利。
ただ、トップページやHomeでの表示ではスクリプトが干渉してうまく出ない場合もあるとのこと。

• 参考サイト o-treetree.hatenablog.com

  atatat.hatenablog.com

• チートシート easy-copy-mathjax.nakaken88.com