zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC177-C「Sum of product of pairs」です。
ポイント
全探索を行うと計算が間に合わないため，メモ化（あらかじめ計算しておいて同じ計算をしない工夫）を施します。今回のメモ化は少しだけ特殊で，「後ろからの累積和」をあらかじめ計算しておくというものです。解法のアイディアを簡単にまとめておきます。
おさえるべき内容
後ろからの累積和の利用
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_rev(i, n) for (int i = n-1; i >= 0; i--)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
int N;
ll A[200020];
ll B[200020];
ll MOD = 1000000007;
int main(){
cin >> N;
rep(i, N) cin >> A[i];
ll ans = 0;
B[N-1] = A[N-1];
// 後ろからの累積和の計算
rep_rev(i, N){
B[i-1] = (B[i] + A[i-1]) % MOD;
}
// メモ化を利用して実際に求めたい部分の計算
rep(i, N-1){
ans += (A[i] * B[i+1]) % MOD;
}
cout << ans % MOD << endl;
}
コメント