地味に2種類の数値を求めさせようとするいやらしい問題。
https://code.google.com/codejam/contest/4244486/dashboard#s=p1
問題
K個のアルファベットからなるキーボードがある。
猿がこのキーボードをS回叩いたとする。
毎回叩くキーはランダムであり、その確率は等しい。
その結果得られる文字列について、目的の単語が何回登場するか(最大値)-(期待値)の値を求めよ。
なお、目的の単語が"ABA"で得られた文字列が"ABABA"である場合、目的の単語は2回登場したとカウントする。
解法
目的の単語から、A-Zの各キーを叩いたときの状態遷移図を作る。
単語の登場数の最大値は、状態遷移図のうち(キーボード中にある文字の中で)最も終端に近い位置のキーを選び続けて行った場合に終端の到達回数を答えればよい。
期待値の方は、各状態の確率をS回分DPで更新していけば良い。
キーボード中の各キーが叩かれる確率は1/Kなので、各キーごとにその確率でキーに対応する次の状態に遷移する。
こちらも終端に到達する確率の総和を求めればよい。
int K,L,S; string KS,LS; int stt[1024][26]; const char base='A'; void CreateSTT(string& pat) { int x,y,z,l=pat.size(); ZERO(stt); FOR(x,l+1) { FOR(y,26) { string pre=pat.substr(0,x)+(char)(base+y); for(z=1;z<=x;z++) if(pre.substr(pre.size()-z) == pat.substr(0,z)) stt[x][y]=z; } if(x!=l) stt[x][pat[x]-base]=x+1; } } int getmax() { int num=0; int cur=0; int i,y; FOR(i,S) { int ma=-1; FORR(c,KS) ma=max(ma,stt[cur][c-'A']); cur=ma; if(cur==L) num++; } return num; } double getexp() { double ret=0; double prob[101][101]; int i,x,y; ZERO(prob); prob[0][0]=1; FOR(i,S) { FOR(x,L+1) if(prob[i][x]) { FORR(c,KS) { int ne=stt[x][c-'A']; if(ne==L) ret += prob[i][x]/K; prob[i+1][ne] += prob[i][x]/K; } } } return ret; } void solve(int _loop) { int f,i,j,k,l,x,y; cin>>K>>L>>S; cin>>KS>>LS; CreateSTT(LS); _P("Case #%d: %.12lf\n",_loop,getmax()-getexp()); }
まとめ
問題文から何を求めるかわかりにくかった。
答えるのは1個の値だけど、最大値と期待値両方求めなければいけないのが厄介。