記事の概要
自分の勉強兼メモでまとめている記事シリーズです。第五弾。
今までの記事はこちら。
| # | 記事 |
|---|---|
| 4 | javaでアルゴリズム入門 - 探索編（bit全探索） |
| 3 | javaでアルゴリズム入門 - 探索編（幅優先探索） |
| 2 | javaでアルゴリズム入門 - 探索編（深さ優先探索） |
| 1 | javaでアルゴリズム入門 - 探索編（全探索、二分探索） |
今回の記事では
- 累積和
について勉強します。
探索編はいったん終了し、別のアルゴリズム（毎週のコンテストで気になったものを）を勉強していきましょう。
累積和
計算のテクニック的なものらしいです。
配列のある区間の総和を求めるのに便利だそう。
一応説明してみますね。
配列aを、{1,3,1,4,7,6,1,0,9}
だとしましょうか。
例えばこの配列の3番目から5番目までの総和を求めなさい、と言われたときを考えます。
通常の求め方
a：{1,3,1,4,7,6,1,0,9} の3~5番目を単純に足し算する。
答えは、1+4+7 = 12
累積和を使用
aの他に、aのi番目までの和を保存しておく配列bを作成する。
b：{0,1,4,5,9,16,22,23,23,32}
a_1をaの1個目の要素みたいな書き方をすると、
b_1 = 0（ここは固定。以降添字は一つずれる）
b_2 = a_1 = 1
b_3 = a_1 + a_2 = 1 + 3 = 4
b_4 = a_1 + a_2 + a_3 = 1 + 3 + 1 = 5
b_5 = a_1 + ... + a_4 = 1 + ... + 4 = 9
b_6 = a_1 + ... + a_5 = 1 + ... + 7 = 16
...
と言った感じです。
このとき、aの3~5番目の総和は次のように求められます。
b_6 - b_3 = 16 - 4 = 12
詳細は以下のとおりです。
b_6 = a_1 + a_2 + a_3 + a_4 + a_5
-)b_3 = a_1 + a_2
--------------------------------------
= a_3 + a_4 + a_5
なんとなくわかりますかね？
前から順番に総和を保存しておくことで、わざわざ3番目 + 4番目 + 5番目、みたいな足算をしなくてもよくなりました！
何が嬉しいのか？
例えば●番目から▲番目までの総和を何度も（●や▲のバリエーションがたくさんある問題を想定）求めなければならないとき、通常の求め方だと、何度も何度もloopを回す必要がありますが、累積和を用いると一発で（O(1)で）総和が求まります。
では問題をみてみましょう。
例題
問題文・入力例などはここをクリックして表示
※できるだけ問題リンクを参照してください
（セクション開始）
【問題文】
長さ N の数列 {ai} と1 以上 N 以下の整数 K が与えられます。 この数列には長さ K の連続する部分列が N−K+1 個あります。これらのそれぞれ部分列に含まれる値の合計の総和を求めてください。
【制約】
入力はすべて整数
1≤K≤N≤10^5
0≤ai≤10^8
【入力】
入力は以下の形式で標準入力から与えられる。
N K
a1 .. aN
【出力】
部分列に含まれる値の合計 N−K+1 個の総和を出力せよ。
（セクション終了）
こんな問題です。
まさに累積和の問題ですね。
K個の足し算をN−K+1回やらなくてはなりません。計算量はO(K * (N-K+1))です。さらに、選び方が悪いと（K = N/2 など）、O(N^2)かかってしまうことがわかります。これでは間に合いません。ということで累積和の出番です。
「K個の足し算をN-K+1回」ですが、累積和を用いれば「K個の足し算」はすべてO(1)で可能となりますので、計算量は大体O(N)で済みます。
方針は以下のとおりです。
- 累積和を保持しておく配列を準備する
- 1~K,2~K+1,3~K+2,...,N-K+1~N のそれぞれの総和を累積和の配列によって求め、最後にその総和を答えとする。
では、以下回答例です。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
long a[] = new long[n]; // 入力を受け取る配列
long b[] = new long[n + 1]; // 累積和を格納
for (int i = 0; i < n; i++) {
// 入力受け取り
a[i] = sc.nextLong();
}
for (int i = 1; i <= n; i++) {
// 累積和計算
b[i] = b[i - 1] + a[i - 1];
}
long ans = 0; // 答え格納
for (int i = 0; i < n - k + 1; i++) {
ans += b[i + k] - b[i];
}
System.out.println(ans);
}
}
・・・う〜ん、添字のところ難しかった。。
特に累積和の一番最初は0にしないといけないのむずいな・・・。
ちょっと練習あるのみですかね。概念とか考え方自体は知れたのでよかったです。
とりあえずここまでにします。それでは〜。