問題
http://community.topcoder.com/stat?c=problem_statement&pm=13694&rd=16318
・ある文字列が与えられる。
・文字列はaからzのアルファベット、もしくは?から成る。
・?の場合、aからzの任意の文字列が入る。
・また、ある文字列が与えられた時、そのスコアは連続する文字列の数となる。
（例）aaabaのスコア aが４つ,aaが２つ、aaaが1つ、bが１つで8
・このとき、与えられた文字列のスコアの期待値を求める。
解き方
スコアがabc・・ではなく、aaa,bbbなど連続した文字列だけでよいので、
実は全探索が可能。
各部分文字列の位置について、aからzのすべての文字列が連続するときの
期待値を求めてあげて足していけばよい。
計算量はO(10^3 * 10~3 * 26)=O(10^7*2.6)なので間に合う。
まずは全探索できないか考える原則にのっとる。
コード
class SquareScores {
public: double calcexpectation(vector<int> p, string s) {
int n=s.size(),m=p.size();
double prob[m];
double ret=0.0;
FORE(i,0,n){
FORE(j,0,m)prob[j]=1.0;
FORE(j,i,n){
if(s[j]=='?'){
FORE(k,0,m)prob[k]*=p[k]*0.01;
}
else{
FORE(k,0,m)if(k!=s[j]-'a')prob[k]=0.0;
}
FORE(k,0,m)ret+=prob[k];
}
}
return ret;
}
};
public: double calcexpectation(vector<int> p, string s) {
int n=s.size(),m=p.size();
double prob[m];
double ret=0.0;
FORE(i,0,n){
FORE(j,0,m)prob[j]=1.0;
FORE(j,i,n){
if(s[j]=='?'){
FORE(k,0,m)prob[k]*=p[k]*0.01;
}
else{
FORE(k,0,m)if(k!=s[j]-'a')prob[k]=0.0;
}
FORE(k,0,m)ret+=prob[k];
}
}
return ret;
}
};