はまやんはまやんはまやん

hamayanhamayan's blog

BuffaloBuffaloBuffalo [SRM723 Div1 Med]

文字列Sがあり、一部'?'となっている。
ある文字列がgoodであるとは、その文字列から部分文字列として"buffalo"を抜き出していくと、全ての文字が抜き出せる文字列である。
'?'を任意の文字列に変えてgoodな文字列を作りたい。何通りあるか(mod10^9+7)

解法

dpで解く。
dp[idx][b][u][a][l][o] := 文字列Sのidx番目まで確定していて、'b'の個数がb個、'u'の個数がu個、'a'の個数がa個、'l'の個数がl個、'o'の個数がo個である時の組合せ。
buffaloに含まれない文字は考慮する必要が無く、fの個数はidx-(b+u+a+l+o)で計算できるので必要ない。
 
これをよくあるDPで更新していけばいいのだが、注意点がgoodな文字列を保つ必要があるということである。
今まで作ってきた文字列がgoodな文字列になれる条件は「b≧uかつ2u≧fかつf≧a*2かつa≧lかつl≧o」である。
そのため、この条件に合わない場合はスキップする。
 
あとは、'?'であるなら、'bufalo'のいずれかを全部試し、そうでないなら、その文字で確定させてカウントしていく。
idx部分は使いまわさないと(多分)MLEする。
あと、メモ化再帰でやってもいいが、mapでメモ化するとTLEする。
しかし、map memo[101]のようにidxの部分だけ別にすると間に合う。
(mapのサイズがある程度小さくなって高速化されるものだと思う)

類題

int mod = 1000000007;
int N;

int dp[2][16][16][16][16][16];

struct BuffaloBuffaloBuffalo {
    int count(string S) {
        N = S.length();

        rep(b, 0, 16) rep(u, 0, 16) rep(a, 0, 16) rep(l, 0, 16) rep(o, 0, 16) dp[0][b][u][a][l][o] = 0;
        dp[0][0][0][0][0][0] = 1;

        rep(idx, 0, N) {
            int i = idx % 2;
            int ii = (idx + 1) % 2;

            rep(b, 0, 16) rep(u, 0, 16) rep(a, 0, 16) rep(l, 0, 16) rep(o, 0, 16) dp[ii][b][u][a][l][o] = 0;

            rep(b, 0, 15) rep(u, 0, 15) rep(a, 0, 15) rep(l, 0, 15) rep(o, 0, 15) {
                int f = idx - (b + u + a + l + o);
                if (b < u or 2 * u < f or f < a * 2 or a < l or l < o) continue;

                if (S[idx] == '?') {
                    dp[ii][b][u][a][l][o] += dp[i][b][u][a][l][o]; dp[ii][b][u][a][l][o] %= mod;
                    dp[ii][b + 1][u][a][l][o] += dp[i][b][u][a][l][o]; dp[ii][b + 1][u][a][l][o] %= mod;
                    dp[ii][b][u + 1][a][l][o] += dp[i][b][u][a][l][o]; dp[ii][b][u + 1][a][l][o] %= mod;
                    dp[ii][b][u][a + 1][l][o] += dp[i][b][u][a][l][o]; dp[ii][b][u][a + 1][l][o] %= mod;
                    dp[ii][b][u][a][l + 1][o] += dp[i][b][u][a][l][o]; dp[ii][b][u][a][l + 1][o] %= mod;
                    dp[ii][b][u][a][l][o + 1] += dp[i][b][u][a][l][o]; dp[ii][b][u][a][l][o + 1] %= mod;
                }
                else if (S[idx] == 'b') dp[ii][b + 1][u][a][l][o] += dp[i][b][u][a][l][o], dp[ii][b + 1][u][a][l][o] %= mod;
                else if (S[idx] == 'u') dp[ii][b][u + 1][a][l][o] += dp[i][b][u][a][l][o], dp[ii][b][u + 1][a][l][o] %= mod;
                else if (S[idx] == 'f') dp[ii][b][u][a][l][o] += dp[i][b][u][a][l][o], dp[ii][b][u][a][l][o] %= mod;
                else if (S[idx] == 'a') dp[ii][b][u][a + 1][l][o] += dp[i][b][u][a][l][o], dp[ii][b][u][a + 1][l][o] %= mod;
                else if (S[idx] == 'l') dp[ii][b][u][a][l + 1][o] += dp[i][b][u][a][l][o], dp[ii][b][u][a][l + 1][o] %= mod;
                else if (S[idx] == 'o') dp[ii][b][u][a][l][o + 1] += dp[i][b][u][a][l][o], dp[ii][b][u][a][l][o + 1] %= mod;
                else return 0;
            }
        }

        
        rep(b, 0, 16) rep(u, 0, 16) rep(a, 0, 16) rep(l, 0, 16) rep(o, 0, 16) {
            int f = N - (b + u + a + l + o);
            if (b == u and b == a and b == l and b == o and 2 * b == f) return dp[N%2][b][u][a][l][o];
        }
        return 0;
    }
};