mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #316 (Div. 2) E. Pig and Palindromes

なんとなく方向性わかっても実装できない…

問題

codeforces.com

解法

基本的には左上からと右下から同時に攻めて行く感じです(同じ文字だったら進軍可能)。

で, これを求めるために dp で解きます。最初に考えたのは
dp[x1][y1][x2][y2] = (左上から攻めた点が今 (x1, y1) 座標にいて, 右下から攻めた点が (x2, y2) 座標にいるとき, これが回文になっている場合の数)
とします。これは O(n^2m^2) なので間に合いません。ですが, 移動回数をひとつの基準にすると,

dp[num][x1][x2] = (num 回進軍していて, 左上から攻めた点の x 座標は x1, 右下から攻めた点の x 座標は x2 となって回文になる場合の数)
とすれば, 計算量的に O((n+m)m^2) となり間に合います。メモリが危ないですが num は直前のだけ覚えていれば良いことを考えるとメモリも削減できます。

const int MAX = 505;
const ll MOD = 1e9+7;
ll dp[2][MAX][MAX];
string field[MAX];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> field[i];
    if (field[0][0] != field[n-1][m-1]) {
        cout << 0 << endl;
        return 0;
    }
    dp[0][0][m-1] = 1;
    int len = (n+m-2)/2;
    for (int i = 0; i < len; i++) {
        int cur = i%2;
        int tar = cur^1;
        memset(dp[tar], 0, sizeof(dp[tar]));
        for (int x1 = 0; x1 < m; x1++) {
            int y1 = i-x1;
            if (y1 < 0) continue;
            for (int x2 = x1; x2 < m; x2++) {
                int y2 = n-1 - i + (m-1-x2);
                if (y2 < 0 || y2 >= n) continue;
                for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) {
                    int nx1 = x1+dx[j];
                    int ny1 = y1+dy[j];
                    int nx2 = x2-dx[k];
                    int ny2 = y2-dy[k];
                    if (nx1 >= m || ny1 >= n || nx2 < 0 || ny2 < 0) continue;
                    if (nx2 < nx1 || ny2 < ny1) continue;
                    if (field[ny1][nx1] != field[ny2][nx2]) continue;
                    (dp[tar][nx1][nx2] += dp[cur][x1][x2]) %= MOD;
                }
            }
        }
    }
    ll ans = 0;
    for (int x = 0; x < m; x++) {
        for (int xx = x; xx < m; xx++) {
            (ans += dp[len%2][x][xx]) %= MOD;
        }
    }
    cout << ans << endl;
    return 0;
}