#はじめに
最近累積和を覚えたのでメモを書き記そうと思います。
Qiitaだけではなく様々なサイトにやり方は掲載されています。しかし、解説者によってそれぞれ自分に合う説明合わない説明があると思うのでこの記事で誰か一人でも理解できた方がいれば嬉しく思います。
また、この記事は初歩の初歩しか説明しません。
#累積和っていつ使うの？
例えば、こんな問題。
Q.９個の自然数が与えられる。その中で連続する３つの和の最大値を求めよ
例えば10個の自然数が「1,2,3,4,5,6,7,8,9」のような昇順だった場合、最後の３つを出力すればいいので計算量はO(1)でいいでしょう。しかし、「1,6,3,8,4,2,9,5,7」のようにバラバラだった場合、累積和を知らないあなただったらどうしますか？
※しゃくとり法を知ってる方は次の章まで読み進めて下さい。
僕だったらこうして全探索してました。（配列のインデックスは0にします・一部配列などC++形式で書きます）
まず、自然数を配列に格納します。
A[9]={1,6,3,8,4,2,9,5,7}
(わかりにくく言葉にします。次に始点をiとしてi=0からi=10-3=7まで動かし、その視点から３つの和を求めて、最大を全探索する）
つまり、こうゆうことです。
i ={0,1,2,3,4,5,6,7,8}
A[i]={1,6,3,8,4,2,9,5,7}
なので
[i=0のとき] [i=4のとき]
A[0]+A[1]+A[2]=1+6+3=10; A[4]+A[5]+A[6]=4+2+9=15;
[i=1のとき] [i=5のとき]
A[1]+A[2]+A[3]=6+3+8=17; A[5]+A[6]+A[7]=2+9+5=16;
[i=2のとき] [i=6のとき]
A[2]+A[3]+A[4]=3+8+4=15; A[6]+A[7]+A[8]=9+5+7=21;←最大値！！！！
[i=3のとき]
A[3]+A[4]+A[5]=8+4+2=14;
この時の計算量を考えてみます。
計算量は配列を参照する回数とすると、7×3=21。
ここで、整数の数をn、m個の和(n>=m)の問題だった場合、計算量は最悪O($n^2$)となってしまいます。
#しゃくとり法使えばいいのでは？
※しゃくとり法を知らない方は次の章まで読み進めて下さい。
確かに、この問題ではしゃくとり法で構いません。しかし、この問題の応用でこのような問題になったらどうでしょうか。
Q.10個の整数が与えられる。その中で連続するm個の和の最大値を求めよ。
自然数が整数に、3個がm個に変わっています。
例えば、10個の整数が正負バラバラだったらどうでしょう。
何個選ぶのが最適解か分かりませんよね？正の数をできるだけ選びたいけど負の数は出来るだけ選びたくない...と良く分からなくなってしまいます。
そうすると、計算量は「どこを始点とするか」×「何個選ぶか」=O($n^2$)=全探索になってしまいます。
#累積和の具体的な考え方
先程の問題で考えます。（順番のインデックスは0とします。）
Q.10個の自然数が与えられる。その中で連続する３つの和の最大値を求めよ
- 自然数10個を並べます。また、配列Bを作り、0を入れます。
配列A: 1 6 3 8 4 2 9 5 7
配列B: 0 - 配列Bの0番目の数(0)と配列Aの0番目(1)の数を足したもの(0+1=1)を配列Bの後ろに付けます。
配列A: 1 6 3 8 4 2 9 5 7
配列B: 0 1 - 配列Bの1番目の数(1)と配列Aの1番目(6)の数を足したもの(1+6=7)を配列Bの後ろに付けます。
配列A: 1 6 3 8 4 2 9 5 7
配列B: 0 1 7 - 配列Bの2番目の数(7)と配列Aの2番目(3)の数を足したもの(3+7=10)を配列Bの後ろに付けます。
配列A: 1 6 3 8 4 2 9 5 7
配列B: 0 1 7 10
つまり、配列Bのn番目の数(B[n])と配列Aのn番目(A[n])の数を足したもの(A[n]+B[n])を配列Bの後ろに付けます。すると、最終的にこうなります。
配列A: 1 6 3 8 4 2 9 5 7
配列B: 0 1 7 10 18 22 24 33 38 45
この配列Bから何が分かるのでしょうか。主に２つあります。
- 例えば配列Bの4番目の18は配列Aの0~3番目の和である。これを一般化すると配列Bのn番目の数は配列Aの0~n-1番目の数の和である。(この事実はあんまり重要ではありません。)
- 例えば配列Aの2番目の数(3)から6番目の数(9)までの和は配列Bの7番目の数(33)から配列Bの2番目の数(7)を引いた数である。これを一般化すると、
配列Aのx番目の数からy番目までの和は、配列Bのy+1番目の数からx番目の数を引いた値である。
(数学好きならこちらを一目見た方が理解しやすいですかね？)
\sum_{k=x}^{y} A[k] = B[y+1]-B[x]
実際に見てみましょう。先程述べた「例えば配列Aの2番目の数(3)から6番目の数(9)までの和は配列Bの7番目の数(33)から配列Bの2番目の数(7)を引いた数である。」では、
\begin{align}
\sum_{k=2}^{6} A[k] = 3 + 8 + 4 + 2 + 9 &= 26\\
B[6+1]-B[2] = 33 - 7 &= 26
\end{align}
一致してるのが分かりと思います。
つまり、
予め記録しておけば連続するm個の和が一瞬で出るんです！！！
#累積和の実装(C++)
三度先程の問題で考えます。
Q.10個の自然数が与えられる。その中で連続する３つの和の最大値を求めよ
まず、必要な変数を宣言します。
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
int n, i, ans = 0;
return 0;
}
次に先程の解説でいうところの配列A（整数を入力する配列）と配列B（累積和を記録する配列）を作成します。
#include <iostream>
#include <algorithm>
using namespace std;
int main(void) {
int n, i, ans = 0;
int A[10], B[11];
B[0] = 0;
for(i = 0; i < 10; i++) cin >> A[i]; //A[10]={1,6,3,8,4,2,9,5,7}
for(i = 1; i < 11; i++) B[i] = A[i - 1] + B[i - 1]; //B[11]={0,1,7,10,18,22,24,33,38,45}
return 0;
}
配列Bでループを回して3つの数の和を求め、最大値を記録します。
ループの初期値が3になっているのは、初期値が2以下の場合A[0] or A[1] or A[0]+A[1]の値しか求めることが出来ない＝３つの数の和を求めることが出来ないからです。
#include <iostream>
#include <algorithm>
using namespace std;
int main(void) {
int n, i, ans = 0;
int A[10], B[11];
B[0] = 0;
for(i = 0; i < 10; i++) cin >> A[i]; //A[10]={1,6,3,8,4,2,9,5,7}
for(i = 1; i < 11; i++) B[i] = A[i - 1] + B[i - 1]; //B[11]={0,1,7,10,18,22,24,33,38,45}
for(i = 3; i < 11; i++) ans = max(ans, B[i] - B[i - 3]); //求めた3つの和がそれまでに求めた数より大きかったらansに代入する
cout << ans << endl; //21
return 0;
}
最初の方で全探索での計算量について私はこう言いました。
この時の計算量を考えてみます。
計算量は配列を参照する回数とすると、7×3=21。
ここで、整数の数をn、m個の和(n>=m)の問題だった場合、計算量は最悪O($n^2$)となってしまいます。
累積和の計算量を考えてみましょう。
計算量は最大値を探すために配列を参照する回数とすると、2*8=16。（例が悪くてごめんなさい）
ここで、整数の数をn、m個の和(n>=m)の問題だった場合、計算量は最悪でもO(n)となります。
そう、$n=10^5$の制約の問題が解けます！！！！
#AtCoderでの演習
AGC023 A-Zero-Sum Ranges
この問題がなかなか良いです。
問題文
長さNの整数列Aがあります。Aの空でない連続する部分列であって、その総和が0になるものの個数を求めてください。 ただし、ここで数えるのは部分列の取り出し方であることに注意してください。つまり、ある2つの部分列が列として同じでも、取り出した位置が異なるならば、それらは別々に数えるものとします。
制約
$1≤N≤2×10^5$
$−10^9≤A_i≤10^9$
入力はすべて整数である。
入力例１を参考に考えていきます。
入力例１
6
1 3 -4 2 2 -2
整数列Aを配列に入れ、その累積和を配列Bに入れます。
A={1,3,-4,2,2,-2}
B={0,1,4,0,2,4,2}
ここで、取り出す部分列の整数の個数をnとすると、
$B[i]-B[i-n]=0$であるiが存在するとき、それは解の候補になります。
例えば、n=3とするとき$B[3]-B[3-3]=0-0=0$なので、i=3で解をもちます。
nが自由に設定できるので、この問題結果的に次のような問題と題意は同じです。
問題文
長さNの整数列Aがあります。整数列Aの累積和を格納した配列をBとすると、Bの中から同じ数字を選ぶ組み合わせはいくつでしょう？
これなら簡単！C++ならsort(B,B+n)とでもしてソートして、同じものの数を数えてあげれば答えが出ます。ただし、例えばB={1,1,1}など同じ数字が3つ以上ある場合について考えてみて下さい。
3つの中から2つ選ぶ方法は高校数学でおなじみ、$_3 C_2 = 3$通りです。このことから、最後に出力するans変数を0で初期化して、同じ数字がn個あった場合、
$ans += n\times(n-1)\div2$というのを繰り返せば、計算量としてはボトルネックがソートになるので、$O(N\log N)$で解けます。
詳しくはAtCoderの解説PDF又は解説動画を見てください。
#まとめ
累積和は制約で$n=10^5$の時などにしょっちゅう出てきます。覚えることで計算量が$O(N^2)⇒O(N)$になるので、Time Limit Exceededで悩んでる方は覚えて損はないはずです。
また、誤字・脱字などあればコメント頂けると幸いです。
最後までご清読頂きありがとうございました。