文字列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
（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; } };
