dwangoプログラミングコンテスト本選 : A - ニコニコ文字列２

Dwangoコン本選のオープンに参加。
時間が短いこともあり、AとB部分点のみ。
http://dwango2015-honsen.contest.atcoder.jp/tasks/dwango2015_finals_1

問題

ニコニコ文字列とは、"25"を１回以上繰り返した文字列であるとする。
N文字の数字からなる文字列Aが与えられる。
ただし一部の文字は未確定("?")である。

このAの部分文字列がニコニコ文字列となるケースがX通り以上あるようなAが何通りあるか。

解法

O(N^2*X)のDPで解ける。
DP[位置][直前の"25"の連続回数][min(X,ニコニコ文字列登場回数)]として各状態の組み合わせを計算していけば良い。
部分文字列としてニコニコ文字列はO(N^2)通り程度存在するが、X回以上は同一視することで計算量を落とすことができる。

int N,X;
ll mo=1000000007;
string S;

ll dp[303][303][303];

ll madd(ll& a,ll b){ (a+=b)%=mo;}

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	cin>>N>>X>>S;
	
	dp[0][0][0]=1;
	FOR(i,N) {
		FOR(y,255) FOR(z,300) if(dp[i][y][z]) {
			ll d=dp[i][y][z];
			
			if(S[i]=='?') {
				if(y%2==0) madd(dp[i+1][y+1][z],d);
				else madd(dp[i+1][1][z],d);
				
				if(y%2==1) madd(dp[i+1][y+1][min(X,z+(y+1)/2)],d);
				else madd(dp[i+1][0][z],d);
				madd(dp[i+1][0][z],8*d);
			}
			else if(S[i]=='2') {
				if(y%2==0) madd(dp[i+1][y+1][z],d);
				else madd(dp[i+1][1][z],d);
			}
			else if(S[i]=='5') {
				if(y%2==1) madd(dp[i+1][y+1][min(X,z+(y+1)/2)],d);
				else madd(dp[i+1][0][z],d);
			}
			else {
				madd(dp[i+1][0][z],d);
			}
		}
	}
	
	ll ret=0;
	FOR(y,257) ret += dp[N][y][X];
	cout<<ret%mo<<endl;
}

まとめ

若干ややこしいけど、理解すればさほど難しくはない。