意外と時間を食った。
http://community.topcoder.com/stat?c=problem_statement&pm=13694
問題
文字列Sのスコアとは、Sの連続した部分文字列のうち、1種類の文字だけで構成されているものの数である。
文字列Sが与えられる。
一部の文字は不明であり、その文字が何であるか確率P[i]が与えられる。
Sのスコアの期待値を求めよ。
解法
以下の2値を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位でもよいのでは。