Google Code Jam 2015 Round 1C : B. Typewriter Monkey

地味に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個の値だけど、最大値と期待値両方求めなければいけないのが厄介。