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

広告

自己紹介

プログラミングとかUTAUとかドット絵とか
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告