Dwangoコン本選のオープンに参加。
時間が短いこともあり、AとB部分点のみ。
http://dwango2015-honsen.contest.atcoder.jp/tasks/dwango2015_finals_1
問題
ニコニコ文字列とは、"25"を1回以上繰り返した文字列であるとする。
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; }
まとめ
若干ややこしいけど、理解すればさほど難しくはない。