AtCoder ARC #059 : F - バイナリハック / Unhappy Hacking

面白かったです。
http://arc059.contest.atcoder.jp/tasks/arc059_d

問題

0,1,Backspaceしかキーがないキーボードがある。
これらのキーボードを計N回打鍵した場合、(3^N)通りの組み合わせのうち、文字列Sを生成するのは何通りか。

解法

まず以下のO(N^3)解法で部分点が取れる。
dp(i,c,w) := i回打鍵後の文字列が、先頭c文字が正しく(Sのprefixと一致する)、その後ろにw文字余計な文字が続いている状態の組み合わせ
上記状態を埋めて遺棄、dp(N,|S|,0)を答えればよい。

満点を取るにはO(N^2)程度にしたいので、なんとか状態を減らそう。
正しい文字余計な文字で文字数を２つ状態に持っているのがもどかしい。
そこで、正しい正しくないは無視して、文字列の文字数だけカウントしよう。
すなわち以下のようになる。

dp(i,c) := i回打鍵後の文字列がc文字である状態の組み合わせ
同様にDPしてdp(N,|S|)を求めると、最終的に|S|文字になる組み合わせ数が求まる。
ここで、こうして作られた|S|文字の文字列のうち、本当にSと一致するものはどれだけあるか考える。
0と1は等確率で打鍵するのだから、dp(N,|S|)のうち1/(2^|S|)個だけがSと一致すると考えて良い。
よってdp(N,|S|)/(2^|S|)を答えればよい。

int N,L;
string S;
ll mo=1000000007;
ll dp[5050][5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	L=S.size();
	
	dp[0][0]=1;
	FOR(i,N) FOR(x,N+1) if(dp[i][x]) {
		(dp[i+1][x+1] += 2*dp[i][x])%=mo;
		(dp[i+1][max(0,x-1)] += dp[i][x])%=mo;
	}
	
	ll ret=dp[N][L];
	FOR(i,L) ret=ret*(mo+1)/2%mo;
	cout<<ret<<endl;
}

まとめ

気づいてしまえば簡単。部分点解法よりも単純。
後で正しい正しくないのつじつまを合わせればいいってのが面白いね。