SRM 636 Div. 1 Easy: ChocolateDividingEasy (2次元の累積和)

解法

kenkoooo.hatenablog.com

以前全探索で解いた問題を2次元の累積和で解き直してみた。実行時間が 1979 ms から 468 ms になった。

コード

import java.util.Arrays;

public class ChocolateDividingEasy {

	public int findBest(String[] chocolate) {
		int H = chocolate.length;
		int W = chocolate[0].length();
		int[][] choco = new int[H + 1][W + 1];

		for (int i = 1; i < choco.length; i++) {
			for (int j = 1; j < choco[i].length; j++) {
				choco[i][j] = Character.getNumericValue(chocolate[i - 1].charAt(j - 1));
			}
		}

		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				choco[i + 1][j + 1] += choco[i + 1][j] + choco[i][j + 1] - choco[i][j];
			}
		}
		int max = 0;

		for (int w1 = 1; w1 < W; w1++) {
			for (int w2 = w1 + 1; w2 < W; w2++) {
				for (int h1 = 1; h1 < H; h1++) {
					for (int h2 = h1 + 1; h2 < H; h2++) {
						int[] chocos = new int[9];
						chocos[0] = choco[h1][w1];
						chocos[1] = choco[h2][w1] - choco[h1][w1];
						chocos[2] = choco[H][w1] - choco[h2][w1];

						chocos[3] = choco[h1][w2] - choco[h1][w1];
						chocos[4] = choco[h2][w2] - choco[h2][w1] - choco[h1][w2] + choco[h1][w1];
						chocos[5] = choco[H][w2] - choco[H][w1] - choco[h2][w2] + choco[h2][w1];

						chocos[6] = choco[h1][W] - choco[h1][w2];
						chocos[7] = choco[h2][W] - choco[h2][w2] - choco[h1][W] + choco[h1][w2];
						chocos[8] = choco[H][W] - choco[H][w2] - choco[h2][W] + choco[h2][w2];

						Arrays.sort(chocos);

						max = Math.max(max, chocos[0]);
					}
				}

			}
		}

		for (int i = 0; i < choco.length; i++) {
			for (int j = 0; j < choco[i].length; j++) {
				System.out.print(choco[i][j] + " ");
			}
			System.out.println();
		}

		return max;
	}

}