TopCoder SRM 615 Div1 Hard AlternativePiles

950ptのHardだけど、550ptのMediumより簡単なのでは…。
http://community.topcoder.com/stat?c=problem_statement&pm=13092

問題

C枚のカードが並んでいる。
各カードは初期状態でR,G,B,Wの4色のいずれかが与えられている。

このうちW色のカードはR,G,Bのいずれかに塗ることができる/塗らなければならない。

その後、C枚のカードを以下のように分類したい。

• 数Mが与えられるので、C枚からB色のカードを取り除いたカードの枚数を2Mの倍数とする。たとえば2MD枚とする。
• 2MD枚のカードの並びを保持したまま、2D枚のM組のカードに分類する。この時各組奇数枚目はR色、偶数枚目はG色としたい。

そのようなW色のカードの塗り分け方は何通りあるか。

解法

まず最初からあるB色のカードは解答に関係しないので外しておく。

まず2MD枚のカードがあったとき、どのような状態なら2つ目の条件を満たせるか考える。
先頭から見ていったとき(R色の枚数-G色の枚数)が0～Mの間であり、最終的にはその差が0になればよい。

よって状態として[R色の枚数-G色の枚数][WをB色に塗った枚数]として数え上げを行い、最後にWをB色に塗った枚数のうち、残りのR,G色のカードが2Mの倍数となるものの総和を取ればよい。

ただ、この場合状態数がO(MC)のため、全体でO(MC^2)の時間がかかる。
自分もO(MC^2)のコードを本番書いてTLEした。

ここで状態のうち[WをB色に塗った枚数]に注目する。
この数を記憶するのは最後にR,G色のカード枚数が2Mの倍数か判定するためである。
よって、WをB色に塗った枚数は2M増えるごとに(R,G色の枚数)mod 2M が循環する。
そのため状態は[WをB色に塗った枚数 % 2M]で良く、全体でO(M^2 C)で処理できる。

ll mo=1000000007LL;
ll dpdp[2][51][102];

class AlternativePiles {
	public:
	int count(string C, int M) {
		string S;
		int nw=0,i,j,k;
		ITR(it,C) if(*it!='B') S+=*it;
		ITR(it,C) if(*it=='W') nw++;
		
		int L=S.size();
		
		ZERO(dpdp);
		dpdp[0][0][0]=1;
		
		
		FOR(i,L) {
			int cur=i&1,tar=cur^1;
			ZERO(dpdp[tar]);
			
			if(S[i]=='R' || S[i]=='W') {
				FOR(j,M) FOR(k,M*2) {
					dpdp[tar][j+1][k] += dpdp[cur][j][k];
					if(dpdp[tar][j+1][k]>=mo) dpdp[tar][j+1][k]-=mo;
				}
			}
			if(S[i]=='G' || S[i]=='W') {
				for(j=M;j>0;j--) FOR(k,M*2) {
					dpdp[tar][j-1][k] += dpdp[cur][j][k];
					if(dpdp[tar][j-1][k]>=mo) dpdp[tar][j-1][k]-=mo;
				}
			}
			if(S[i]=='W') {
				FOR(j,M+1) FOR(k,M*2) {
					int kk=(k+1)%(2*M);
					dpdp[tar][j][kk] += dpdp[cur][j][k];
					if(dpdp[tar][j][kk]>=mo) dpdp[tar][j][kk]-=mo;
				}
			}
		}
		
		ll ret=0;
		FOR(i,2*M) if(((L-i)%(2*M))==0) ret += dpdp[L%2][0][i];
		
		return ret%mo;
		
	}
};

まとめ

R色-G色がM以下でよい、という点までは本番たどり着けたので行けたと思ったんだけどなぁ。