TopCoder SRM 654 Div1 Easy SquareScores

意外と時間を食った。
http://community.topcoder.com/stat?c=problem_statement&pm=13694

問題

文字列Sのスコアとは、Sの連続した部分文字列のうち、１種類の文字だけで構成されているものの数である。

文字列Sが与えられる。
一部の文字は不明であり、その文字が何であるか確率P[i]が与えられる。
Sのスコアの期待値を求めよ。

解法

以下の２値をDPで更新していく。

• i文字目の末尾の文字がcである確率
• i文字目の末尾の文字がcであり、直前何文字cが続くかの期待値

後者は前者の値による重みづけを行いながら更新する。
また、後者の値を更新しながら、答えである部分文字列数の期待値に足しこんでいく。

class SquareScores {
	public:
	double calcexpectation(vector <int> p, string s) {
		int i,x,L=s.size(),y;
		double P[1010][26]={};
		double ret=1;
		double dpL[1010][26]={};
		double dpP[1010][26]={};
		
		
		FOR(i,L) {
			if(s[i]!='?') P[i][s[i]-'a']=1;
			else FOR(x,p.size()) P[i][x]=p[x]/100.0;
		}
		FOR(x,26) dpL[0][x]=1, dpP[0][x]=P[0][x];
		
		for(i=1;i<=L-1;i++) {
			FOR(x,26) FOR(y,26) {
				double tp=dpP[i-1][x]*P[i][y];
				dpP[i][y] += tp;
				dpL[i][y] += tp*(1+((x==y)?dpL[i-1][x]:0));
				ret += tp*(1+((x==y)?dpL[i-1][x]:0));
			}
			FOR(x,26) if(dpP[i][x]) dpL[i][x]/=dpP[i][x];
		}
		return ret;
		
	}
}

まとめ

Div1 Easyにしては若干ややこしい問題。
275pt位でもよいのでは。