白駿11660、区間と5-DPを求めて、累計と

38285 ワード
どうてきけいかくほう DP dynamic programming アルゴリズム#アルゴリズム# 累加 白駿11660区間求和5 コーディングテスト テキストリンク

https://www.acmicpc.net/problem/11660
プール①- 1行あたりのストレージ積算と
1.アイデア

  • マトリクスを入力すると、各行の累計和が計算されます.
  • 1行累加元素,2行累加元素,...,n行累加要素
  • int[][] sum

  • 領域(x1, y1)(x2, y2)の和
    =(行x1x2の累加)-(行x1x2の列1y1-1の累加)
    = ( sum[x1][y2] + ... + sum[x2][y2] ) - ( sum[x1][y1 - 1] + ... + sum[x2][y1 - 1] )
    • 注意:行、列の入力(x1, y1),(x2, y2)上xが行、yが列
    2.資料構造
  • int[][] map:入力マトリクス
    =>メモリ:n x n x 4 byte
    =>n置換最大値:2^20 x 4バイト=4194304バイト~=4 MB
  • int[][] sum:各行累計
    =>sum[i][n]=map[i][1]map[i][n]と
    =>sum[i][n]の最大値=10^3 xn
    =>最大10^3 x 1024<<21億、int
  • Area[]:入力エリア(x1, y),(x2, y2)
    • 3.時間複雑度

  • 1つの入力領域に対して和を求める:for文x1行~x2行
    =約O(x 2-x 1)
    =>Worst最初の行から最後の行への確認
    = O(n)

  • m個の入力領域の和=最短O(n x m)
    =>n、mは最大値を表します:2^10 x 10^5=102400000
    • 各テストケースの各部分の合計を計算するだけです.
  • O(m x n^2)
    =>m,n置換最大値:10^5 x 2^20>>1億(タイムアウト)
    • コード#コード#
    import java.io.*;
import java.util.StringTokenizer;

class Area {
	// x가 행, y가 열
	public int x1, y1;
	public int x2, y2;

	public Area(int x1, int y1, int x2, int y2) {
		this.x1 = x1;
		this.y1 = y1;
		this.x2 = x2;
		this.y2 = y2;
	}
}

public class Main_Sum {
	static int n;					// n x n 행렬
	static int m;		 			// 합을 구하는 횟수
	static int[][] map;
	static Area[] areas;			// 입력 구간 (x1, y1), (x2, y2)
	static int[][] sum;				// 각 행마다 누적합
	static StringBuilder sb = new StringBuilder();

	static void solution() {
		for (Area area : areas) {
			int result = 0;				// 출력

			for (int i = area.x1; i <= area.x2; i++) {
				// 1. 행 x1 ~ x2 의 누적합
				// = sum[x1][y2] + ... + sum[x2][y2]
				result += sum[i][area.y2];

				// 2. (행 x1 ~ x2 의 누적합) - (행 x1 ~ x2 에서 열 1 ~ y1-1 의 누적합)
				// = (sum[x1][y2] + ... + sum[x2][y2]) - (sum[x1][y1 - 1] + ... + sum[x2][y1 - 1])
				if (area.y1 - 1 >= 1)
					result -= sum[i][area.y1 - 1];
			}

			sb.append(result).append("\n");
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		map = new int[n + 1][n + 1];			// [1][1] ~ [n][n] 사용
		sum = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());

			int temp = 0;
			for (int j = 1; j <= n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());

				temp += map[i][j];
				sum[i][j] = temp;
			}
		}

		areas = new Area[m];
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());

			areas[i] = new Area(x1, y1, x2, y2);
		}

		solution();
		System.out.println(sb);
	}
}
    解②- DP転送値による累積計算
    1.アイデア
    DPアレイによる累積表示
    1)DP方式の保存

  • ①DPシナリオ定義dp[i][j]:map[1][1]|map[i][j]の累計和

  • ②点火式dp[i][j] = ( dp[i-1][j] + dp[i][j-1] ) - dp[i-1][j-1] + map[i][j](dp[i-1][j-1]:重複部分、map[i][j]:入力マトリクスの要素)
    • 2)入力区間(x1, y1)(x2, y2)と
  • dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
  • dp[x1-1][y2]:入力エリア上方
  • dp[x2][y1-1]:入力エリア左側
  • dp[x1-1][y1-1]:繰り返し
    • 注意:行、列の入力(x1, y1),(x2, y2)上xが行、yが列
    2.資料構造
  • int[][] map:入力マトリクス
    =>メモリ:n x n x 4 byte
    =>n置換最大値:2^20 x 4バイト=4194304バイト~=4 MB
  • int[][] dp:DPアレイ、面積積算
    =>最大要素値:dp[n][n]=n x n x 10^3=2^20 x 10^3<<21億、int
  • Area[]:入力エリア(x1, y),(x2, y2)
    • 3.時間複雑度
    1)入力マトリクスmapDP配列を保存
  • O(n^2)
    • 2)DPアレイを用いて入力区間の和を計算する
  • O(m)
    • =>全時間複雑度:O(n^2+m)
    =>n,m代入最大値:2^20+10^3<1億
    各テストケースの各部分の合計を計算するだけです.
  • O(m x n^2)
    =>m,n置換最大値:10^5 x 2^20>>1億(タイムアウト)
    • コード#コード#
    import java.io.*;
import java.util.StringTokenizer;

class Area {
	// x가 행, y가 열
	public int x1, y1;
	public int x2, y2;

	public Area(int x1, int y1, int x2, int y2) {
		this.x1 = x1;
		this.y1 = y1;
		this.x2 = x2;
		this.y2 = y2;
	}
}

public class Main_DP {
	static int n;					// n x n 행렬
	static int m;		 			// 합을 구해야하는 횟수
	static int[][] map;
	static Area[] areas;			// 입력 구간 (x1, y1), (x2, y2)
	static int[][] dp;				// DP 배열, dp[i][j]: [1][1] ~ [i][j] 까지의 누적합
	static StringBuilder sb = new StringBuilder();

	static void solution() {
		// 2) 각 입력 구간의 합 계산
		for (Area area : areas) {
			// dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
			int result = dp[area.x2][area.y2]
					- dp[area.x1 - 1][area.y2] - dp[area.x2][area.y1 - 1]
					+ dp[area.x1 - 1][area.y1 - 1];

			sb.append(result).append("\n");
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		map = new int[n + 1][n + 1];			// [1][1] ~ [n][n] 사용
		dp = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());

			// 1) 행렬 map 입력하면서, DP 배열 저장
			for (int j = 1; j <= n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				dp[i][j] = (dp[i-1][j] + dp[i][j-1]) - dp[i-1][j-1] + map[i][j];
			}
		}

		areas = new Area[m];
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());

			areas[i] = new Area(x1, y1, x2, y2);
		}

		solution();
		System.out.println(sb);
	}
}
    Redis Internals (strings)
    Springboot統合redisストレージセッション