読者です 読者をやめる 読者になる 読者になる

Codeforces Round #316 Div2 E: Pig and Palindromes

問題

codeforces.com

解法

dp[h][w][rh][rw]:=(h,w)を通り、(rh,rw)を通る経路が回文である経路数を持たせたいがメモリが足りない。しかし、(1,1)と(h,w)、(H,W)と(rh,rw)の距離を両方mとして、mを少しずつ小さくしていくようにすれば、dp[h][rh]だけを保存すれば良いことになる。

コード

import java.util.Scanner;

public class Main {
	private final int MOD = (int) 1e9 + 7;

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int H = scanner.nextInt();
		int W = scanner.nextInt();

		int N = Math.max(H, W) + 1;
		char[][] map = new char[N][N];
		for (int i = 1; i <= H; i++) {
			char[] str = scanner.next().toCharArray();
			for (int j = 1; j <= W; j++) {
				map[i][j] = str[j - 1];
			}
		}
		scanner.close();
		/*
		 * dp[h][rh]:= 高さhにあり、(1,1)からマンハッタン距離mにある点(h,w)が、
		 * (H,W)からマンハッタン距離mにある点(rh,rw)と接続した時に回文になる経路の数
		 */
		int[][] dp = new int[N][N];

		// (1,1)からマンハッタン距離MOVESの位置にある(h,w)について考える
		int MOVES = H + W - 2;
		MOVES /= 2;// (h,w)と(rh,rw)が隣り合うか一致するようにMOVESを設定する
		for (int h = 1; h <= H; h++) {
			int w = MOVES - h + 2;
			// (H,W)からマンハッタン距離MOVESの位置にある(rh,rw)についても考える
			for (int rh = 1; rh <= H; rh++) {
				int rw = W - (MOVES - (H - rh));
				if (w < 0 || rw < 0 || w >= N || rw >= N) {
					// 場外だったらスルー
					continue;
				}
				if (h > rh || w > rw) {
					// (h,w)から(rh,rw)へ到達不可能な場合
					dp[h][rh] = 0;
				} else if (map[h][w] != map[rh][rw]) {
					// (h,w)と(rh,rw)を結ぶ経路が回文でない時
					dp[h][rh] = 0;
				} else {
					dp[h][rh] = 1;
				}
			}
		}

		for (int m = MOVES - 1; m >= 0; m--) {
			// (1,1)からマンハッタン距離mの位置にある(h,w)について考える
			for (int h = 1; h <= H; h++) {
				int w = m - h + 2;
				// (H,W)からマンハッタン距離mの位置にある(rh,rw)についても考える
				for (int rh = H; rh >= 0; rh--) {
					int rw = W - (m - (H - rh));
					if (w < 0 || rw < 0 || w >= N || rw >= N) {
						// 場外だったらスルー
						continue;
					}

					if (h > rh || w > rw) {
						// (h,w)から(rh,rw)へ到達不可能な場合
						dp[h][rh] = 0;
					} else if (map[h][w] != map[rh][rw]) {
						// (h,w)と(rh,rw)を結ぶ経路が回文でない時
						dp[h][rh] = 0;
					} else {
						dp[h][rh] += dp[h][rh - 1];
						dp[h][rh] %= MOD;
						dp[h][rh] += dp[h + 1][rh];
						dp[h][rh] %= MOD;
						dp[h][rh] += dp[h + 1][rh - 1];
						dp[h][rh] %= MOD;
					}
				}
			}
		}
		System.out.println(dp[1][H]);

	}

	public static void main(String[] args) {
		new Main().solve();
	}

}