SRM723 Lv2 : BuffaloBuffaloBuffalo
作成日：2017.11.19
最終更新日：2017.11.19
問題概要
文字列$A$が2つの文字列$B$,$C$の交互配置であるとは、文字列$A$から順序を保ったまま文字列$B$を抜き出すことができ、抜き出した時にできる文字列が$C$になることをいう。
3つ以上の文字列の交互配置も同様に定義される。
$pattern$は英小文字と$?$からなる文字列が与えられ、$?$には任意の英小文字で置き換えることができる。
$pattern$が1つ以上の"buffalo"の交互配置となるような$?$の置き換え方を$mod \: 10^9 + 7$で求めよ。
制約
$1 \leq |pattern| \leq 100$
$pattern$は英小文字または$?$からなる
考え方
$|pattern|$が$7$の倍数でない時の答えは明らかに$0$であるから、以下ではこの場合を除外する。
$pattern$を$i$文字目まで見た時の文字$*$の登場回数を$t_i(*)$とし、$n = |pattern|$とする。
条件を言い換えると、$t_i(b)$$\geq t_i(u)$$\geq t_i(f)/2$$\geq t_i(a)$$\geq t_i(l)$$\geq t_i(o)$かつ$t_n(o) = n/7$となる。
$t_i(*)$$(* = b,u,f,a,l,o)$の値を持つDPを考えると、$\sum_*{t_i(*)} = i$であることから状態数は$O((n/7)^6)$である。
遷移も各状態につき高々$6$個であるから、十分高速である。
ソースコード
マクロ等はこちら
const LL mod = 1e9 + 7;
const int MC = 15;
class BuffaloBuffaloBuffalo {
LL dp[MC][MC][MC*2][MC][MC][MC];
string S;
LL ans(int b , int u , int f , int a , int l , int o){
LL &x = dp[b][u][f][a][l][o];
if(x >= 0) return x;
int z = b + u + f + a + l + o - 1;
x = 0;
if(b>u) if(S[z]=='b' || S[z]=='?') (x += ans(b-1,u,f,a,l,o)) %= mod;
if(u>(f+1)/2) if(S[z]=='u' || S[z]=='?') (x += ans(b,u-1,f,a,l,o)) %= mod;
if((f+1)/2>a) if(S[z]=='f' || S[z]=='?') (x += ans(b,u,f-1,a,l,o)) %= mod;
if(a>l) if(S[z]=='a' || S[z]=='?') (x += ans(b,u,f,a-1,l,o)) %= mod;
if(l>o) if(S[z]=='l' || S[z]=='?') (x += ans(b,u,f,a,l-1,o)) %= mod;
if(o) if(S[z]=='o' || S[z]=='?') (x += ans(b,u,f,a,l,o-1)) %= mod;
return x;
}
public:
int count(string pattern) {
S = pattern;
int n = S.size();
if(n%7) return 0;
repp(b,0,MC) repp(u,0,MC) repp(f,0,MC*2) repp(a,0,MC)
repp(l,0,MC) repp(o,0,MC) dp[b][u][f][a][l][o] = -1;
dp[0][0][0][0][0][0] = 1;
int m = n/7;
return ans(m,m,m*2,m,m,m);
}
};解法まとめ
$t_i(*)$の値を状態に持つDPを行う。(8-20行)
SRM723の他の問題 Lv1 Lv3