Code Formula 2014 予選A : D - 無刻印キーボード

意外とあっさり解けた。
http://code-formula-2014-quala.contest.atcoder.jp/tasks/code_formula_2014_qualA_d

問題

無刻印のキーボードがあり、0～9とa～zのキーはそれぞれどの文字がどこにあるか叩いてみないとわからない。

ここで文字列Sの文字を先頭から順に入力したい。
１文字ずつキーを叩いた際、Sと一致しない文字が出た場合はバックスペースを押して１文字戻らなければいけない。

0～9及びa～zのキーの位置のうち、一部はすでに判明している。
最適な戦略でキーを叩いたときSを入力しきる最少ない打鍵数の期待値を答えよ。

解法

S中ですでに判明している文字および、S中での登場回数が2回目以降の文字を入力する際は、そのキーの位置は判明しているので１キーで確実に入力できる。
残りは、位置未確定の文字がC個あるうち、L個を順に入力するのにかかる打鍵数を求めることになる。

これをf(L,C)とする。
f(L,C)は以下のように考えて漸化式で表現できる。

• 未確定文字C個のうち１個キーを叩くと：
  • 1/Cの確率で次に入力すべき文字のキーにヒットする。その際必要な打鍵数は(1+f(L-1,C-1) )。
  • (L-1)/Cの確率で、次ではないが後で入力すべき文字のキーにヒットする。その際は一度バックスペースで戻るのと、後でそのキーが登場した際は１打確定で入力できるので、打鍵数は(3+f(L-1,C-1) )
  • (C-L)/Cの確率で、不要な文字のキーにヒットする。その際は一度バックスペースで戻って未確定文字を１個減らすので、打鍵数は(2+f(L,C-1))。

よってこれらを確率で重みづけ平均を取ったf(L,C)=( (1+f(L-1,C-1) ) + (3+f(L-1,C-1) )*(L-1) + (2+f(L,C-1) )*(C-L) ) / Cとなる。

string S,S2;
string K;
int ok[256],id[256],unk,kn;
double memo[51][51];

double dodo(int left,int cand) {
	int i,j;
	if(left==0) return 0;
	if(left>cand) return 0;
	if(memo[left][cand]>=0) return memo[left][cand];
	
	memo[left][cand]=(1+dodo(left-1,cand-1))/cand + (3+dodo(left-1,cand-1))*(left-1)/cand + (2+dodo(left,cand-1))*(cand-left)/cand;
	
	return memo[left][cand];
}

void solve() {
	int f,i,j,k,l,x,y;
	int ret=0;
	cin>>S>>K;
	unk=36-K.size();
	ITR(it,K) ok[*it]=1;
	MINUS(id);
	
	FOR(x,51) FOR(y,51) memo[x][y]=-1;
	
	FOR(i,S.size()) {
		if(ok[S[i]]) ret++;
		else {
			ok[S[i]]=1;
			kn++;
		}
	}
	_P("%.12lf\n",ret+dodo(kn,unk));
}

まとめ

これは本番割とすぐ思いつけた。