AtCoder Regular Contest 059 F - バイナリハック / Unhappy Hacking

問題

arc059.contest.atcoder.jp

解法

まず部分点解法を考えます。

dp[n][m][now] = (すでに n 回キーを押したときに, 目標の文字列と m 番目までは一致していて, 生成されている文字は now 個であるような場合の数) という dp をします。これは各状態で 0 を押すか, 1 を押すか, BackSpace を押すかで場合分けすれば簡単に遷移ができるので O(N^3) です。

満点解法では, 文字列 s があって, これを空文字にするように遷移していくことを考えます。

例えば 001001 という文字があったとすると,

• その前は BackSpace を押していた -> 右に 0 か 1 を追加する(0010010 or 0010011)
• その前は文字を追加していた -> 1 を追加する(00100 という文字列だった)

というような遷移があります。空文字列の場合は少し違って, 前に BackSpace を押していた場合にその前もやはり空文字列なこともあるし前の文字は 0 か 1 だったということもあります。

このように考えると, 文字列 s になにが書いてあったかは関係なく, 文字列の長さだけが重要であることに気付きます。この dp は O(N^2) でできるので満点を取ることができます。

const int MAXN = 5050;
const int MOD = 1e9+7;
int N, M;
string s;
ll dp[MAXN][MAXN];

ll dfs(int n, int m) {
    ll& ret = dp[n][m];
    if (ret >= 0) return ret;
    if (n == N) {
        if (m == 0) return ret = 1;
        else return ret = 0;
    }
    ret = 0;
    // Back
    if (m+1 < MAXN) {
        ret += 2*dfs(n+1, m+1);
    }
    if (m == 0) {
        ret += dfs(n+1, m);
    }
    // other
    if (m > 0) {
        ret += dfs(n+1, m-1);
    }
    ret %= MOD;
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    cin >> s;
    M = s.size();
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, M) << endl;
    return 0;
}