ヘクトのメモ

なんとなくいろいろ書いていくと思います.

SRM 654

Div1 Easy SquareScores

問題
a-zと?で構成される文字列Sが与えられる.そして,?は0-indexedでi番目のアルファベットにp[i]%の確率で変換される.
この時,1種類のアルファベットで構成されているSの連続した部分文字列の数の期待値を求めよ


解法
区間 [l,r)が1種類のアルファベットまたは?で構成できるかを調べる.
ここで,この区間の中の?の数をmとおく.
i番目のアルファベットで構成できる場合は,p[i]^mの確率で構成できる.
?で構成できる場合は,Σ(p[i]^m)の確率で構成できる.


これを元に,全ての区間を幅が小さい方から計算して確率を足し合わせていく.


計算量はO(n^2)

char memo[1010][1010];
double pro[27][1010];
int num[1010][1010];

class SquareScores {
public:
	double calcexpectation(vector <int> p, string s) {
		int n=p.size();
		int m=s.size();
		rep(i,m+1)rep(j,m+1) memo[i][j]=-1,num[i][j]=0;

		rep(i,m){
			memo[i][i+1]=s[i];
			if(s[i]=='?') num[i][i+1]=1;
		}
		for(int d=2;d<=m;++d){
			for(int i=0;i+d<=m;++i){
				int l=i,r=i+d;
				if(memo[l][r-1]==-1)
					continue;
				if(s[r-1]=='?'){
					memo[l][r]=memo[l][r-1];
					num[l][r]=num[l][r-1]+1;
				}else if(memo[l][r-1]=='?'){
					memo[l][r]=s[r-1];
					num[l][r]=num[l][r-1];
				}else if(memo[l][r-1]==s[r-1]){
					memo[l][r]=s[r-1];
					num[l][r]=num[l][r-1];
				}else
					memo[l][r]=-1;
			}
		}

		rep(i,n) pro[i][0]=1.0;
		rep(i,n) rep(j,m) pro[i][j+1]=pro[i][j]*1.0*p[i]/100;
		rep(j,m+1) rep(i,n) pro[n][j]+=pro[i][j];

		double ans=0.0;
		rep(i,m)rep(j,m+1) if(memo[i][j]!=-1){
			int index=-1;
			if(memo[i][j]=='?')
				index=n;
			else
				index=memo[i][j]-'a';
			double cur=pro[index][num[i][j]];
			ans+=cur;
		}
		return ans;
	}
};