Codeforces Round #316 Div2 E: Pig and Palindromes
解法
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(); } }