TopCoder SRM 558 Div1 Easy Stamp

ああ、x--とまたやらかしてしまった。
しかも終了直後にEasyとMediumが通るというひどさ。

Easyは不等号のミス。
時間切れだったとはいえ、Mediumがノーヒントで解けたのでよしとしておこう…。

(URLは掲載まち)

RGB*で構成される文字列を、長さLの文字列を使って構成していく。
1<=L<=(文字列長)でループさせて、最小コストを求めていく。

長さLの文字列を何回使って元の文字列が構築できるか、DPで求める。
状態としては[現在の位置][スタンプ開始位置(0～(L-1)文字前)][RGBで3通り]分ある。

class Stamp {
	public:
	int N;
	int col[51];
	int dp[51][51][3];
	int large;
	
	int calc(int L) {
		int x,z,cc,y;
		large=1<<29;
		ZERO(dp);
		
		if(L==1) return N;
		//_P("do %d\n",L);
		FOR(x,N+1) FOR(z,N) {
			dp[x][z][0]=dp[x][z][1]=dp[x][z][2]=large;
		}
		FOR(z,N) {
			dp[0][z][0]=dp[0][z][1]=dp[0][z][2]=0;
		}
		
		
		
		FOR(x,N) {
			if(x <= N-L) {
				//新規にL文字置く
				
				cc=min(dp[x][0][0],dp[x][0][1]);
				cc=min(cc,dp[x][0][2]);
				cc++;
				if(cc<large) {
					FOR(z,3) {
						int ok=1,l;
						FOR(l,L) if(col[l+x] >0 && col[l+x]!=z+1) ok=0;
						if(ok) {
							//_P("%d %d %d\n",x,L,z);
							FOR(l,L){
								dp[x+l+1][L-(l+1)][z] = min(dp[x+l+1][L-(l+1)][z],cc);
								//_P("set %d %d %d\n",x+l+1,L-(l+1),dp[x+l+1][L-(l+1)][z]);
							}
						}
					}
				}
			}
			
			FOR(y,L) {
				if(x-y<0) continue;
				if(x-y+L>N) continue;
				FOR(z,3) {
					if(dp[x-y][y][z]>=large) continue;
					cc=dp[x-y][y][z]+1;
					//_P("do %d %d %d %d\n",x,y,z,cc);
					int ok=1,l;
					FOR(l,L) if(col[x-y+l] >0 && col[x-y+l]!=z+1) ok=0;
					if(ok) {
						FOR(l,L) dp[x-y+l+1][L-(l+1)][z] = min(dp[x-y+l+1][L-(l+1)][z],cc);
					}
				}
			}
		}
		
		cc=large;
		cc=min(cc,dp[N][0][0]);
		cc=min(cc,dp[N][0][1]);
		cc=min(cc,dp[N][0][2]);
		return cc;
	}
	
	int getMinimumCost(string desiredColor, int stampCost, int pushCost) {
		int i,c;
		N=desiredColor.size();
		FOR(i,N) {
			if(desiredColor[i]=='*') col[i]=0;
			if(desiredColor[i]=='R') col[i]=1;
			if(desiredColor[i]=='G') col[i]=2;
			if(desiredColor[i]=='B') col[i]=3;
		}
		int minc=1<<29;
		
		for(i=1;i<=N;i++) {
			c=calc(i);
			if(c>=large) continue;
			minc=min(minc, i*stampCost + c*pushCost);
		}
		return minc;
		
	}
};

まとめ

本番では途中のx-y+L>Nを>=Nとして間違えた。
まぁ本番ミスしたとはいえDPがちゃんと書けて良かった。

これ、最初複数のスタンプ使ってコスト最小化するのかと思ってえらい焦った。
でもこれ、250じゃなくて275とはいえ、いつものEasyよりだいぶ難しいな…。