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; } };