累積和について

AtCoderの記事です。

今回は累積和について学習しました。

前回のABCの結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

なかなか思うように進まないことも多いですが、焦らず着実に進めていきます。

累積和とは

累積和とは、その名の通り、配列などで初めの値からそこまでの和を記録するものです。

使い方としては、ある区間の和を複数回求める必要があるときに使います。

これを行うと前処理にO(N)かかりますが、値を取り出すときはO(1)で取り出せるので、計算量の削減ができます。

どのように解くのか（Javaの場合）

基本的には累積和を格納する用の配列を用意し、あらかじめ累積和を格納します。

このとき、配列の大きさはN+1にしないといけないことに注意が必要です。

大まかなテンプレは次の通りです。

//前処理
int[] a = new int[n];
int[] sum = new int[n+1];
sum[0] = 0;
for(int i=0; i<n; i++) {
	a[i] = sc.nextInt();
	sum[i+1] = sum[i] + a[i];
}

//最大値を求める
int max = 0;
for(int i=1; i<=n-k+1; i++) {
	//取り出し
	int s = sum[i+k-1] - sum[i-1];
	max = Math.max(max, s);
}

//処理

テンプレは正直問題によって違うので難しいですね。

これを応用した2次元累積和もあります。

実際に問題を２つ解いてみました。

１つめは AGC023のA問題 Zero-Sum Ranges です。
atcoder.jp

解法は分かったのですが、nCrの求め方をライブラリで求めようとしてはまりました。

今回はr=2なので、公式通りに計算すればエラーなく通ります。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		long[] sum = new long[N+1];
		int max = 0;
		sum[0] = 0;
		Map<Long, Integer> count = new HashMap<>();
		count.put(0L, 1);
		for(int i=1; i<=N; i++) {
			sum[i] = sum[i-1] + sc.nextLong();

			if(count.containsKey(sum[i])) {
				int new_c = count.get(sum[i])+1;
				count.put(sum[i], new_c);
				max = Math.max(max, new_c);
			}
			else {
				count.put(sum[i], 1);
				max = Math.max(max, 1);
			}
		}

		long ans = 0;
		for(int value : count.values()) {
			ans += (long)value * (value-1) / 2;
		}

		System.out.println(ans);
	}
}

もう1つは、2次元累積和の問題で、ABC005のD問題 おいしいたこ焼きの焼き方 です。
atcoder.jp

やはり難しい。

水色diffということもあってか、一筋縄ではいきません。

問題の意味を間違えてとらえていたのと、最大値の更新の式を間違え、かなりの時間格闘しました。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		int[][] D = new int[N][N];
		int[][] sum = new int[N+1][N+1];
		sum[0][0] = 0;
		sum[0][1] = 0;
		sum[1][0] = 0;

		//2次元累積和
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				D[i][j] = sc.nextInt();
				sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + D[i][j];
			}
		}

		//面積がN*N以下のたこ焼きの美味しさの合計の最大値
		int[] delis = new int[N*N+1];
		Arrays.fill(delis, 0);
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				int max = 0;
				int area = i * j;
				for(int k=0; k<=N-i; k++) {
					for(int l=0; l<=N-j; l++) {
						int deli = sum[k+i][l+j] - sum[k+i][l] - sum[k][l+j] + sum[k][l];
						max = Math.max(max, deli);
					}
				}

				delis[area] = Math.max(delis[area], max);
				//面積がarea以上の値について最大値を更新
				for(int k=area+1; k<=N*N; k++) {
					delis[k] = Math.max(delis[k], delis[area]);
				}
			}
		}

		int Q = sc.nextInt();
		int[] ans = new int[Q];
		for(int i=0; i<Q; i++) {
			int P = sc.nextInt();

			ans[i] = delis[P];
		}

		for(int i=0; i<Q; i++) {
			System.out.println(ans[i]);
		}
	}
}

ということで、累積和についてでした。

2次元累積和についてはまだ練習が必要ですね。

いもす法やしゃくとり法についてはまた今度やります。

このあと、21:00からABCがあるので、頑張ります。