TopCoderOpen 2015 Round1C Hard DevuAndBeautifulSubstrings

EasyやMediumよりも早く解けた…。
http://community.topcoder.com/stat?c=problem_statement&pm=13731

問題

美しいバイナリ文字列とは、01が交互に登場する文字列であるとする。

N文字のバイナリ文字列のうち、その全部分文字列のうち美しいバイナリ文字列となるものがcnt通りとなるようなものの数を求めよ。

解法

直前にx文字の美しいバイナリ文字列があるとき、末尾に1文字追加すると、その新規追加文字を末尾とするような美しい部分文字列を(x+1)個余分に作れるようになる。

この考察をもとに、dp[文字位置][ここまで美しい部分文字列の合計][直前の美しい文字列の長さ]=前記状態を満たす文字列の数、としてDPしていけばよい。

DPの時は、美しい文字列を1文字延長できる場合(直前の文字と別の文字を追加する場合)と延長できない場合(直前と同じ文字を追加する場合)で計算していくだけ。

ll dp[2][2500][51];

class DevuAndBeautifulSubstrings {
	public:
	long long countBeautifulSubstrings(int n, int cnt) {
		int i,x,y;
		ZERO(dp);
		dp[0][0][0]=1;
		FOR(i,n) {
			int cur=i%2,tar=cur^1;
			ZERO(dp[tar]);
			FOR(x,1300) FOR(y,51) if(dp[cur][x][y]) {
				dp[tar][x+y+1][y+1] += dp[cur][x][y];
				dp[tar][x+1][1] += dp[cur][x][y];
			}
		}
		ll ret=0;
		FOR(x,51) ret += dp[n%2][cnt][x];
		return ret;
	}
}

まとめ

Mediumは実装は簡単でも問題文を解釈する部分で一ひねりあったけど、こちらはヒネリも何もないな。