TopCoder SRM 493 Div 1 Medium AmoebaCode

問題概要

0〜Kの数字からなる文字列が与えられる。
文字列のそれぞれの0を、好きな1〜Kの数字に置き換えて、
「任意の同じ数字のペア間の距離の最小値」を最大にしたい。

そのような最大値を求めよ。文字列の文字数は50以下、Kは7以下である。

解法

答えの上限はKである。（使える文字がK種類なので、K回以内に同じ文字が来る）
よって距離の最小値に影響があるのは今見てる文字からK-1文字。

6文字を覚えるDPをすればよい。
Kは7以下であるので3ビットで表現してやる。
dp[i][j]にi文字目まで見て、最後の6文字の状態がjのときの最適解。

jの中に新しい数字dが何番目に最初に出てくるかはあらかじめ計算しておく。

計算量

O(N * 8^K-1 * K).
ループは最悪ケースで9000万回くらい。
システムテストの最悪ケースは750ms弱。

ソースコード

int n,dp[51][1<<18],cost[1<<18][8],cd[50];

class AmoebaCode {
	public:
	int find(string code, int K) 
	{
		n=code.size();
		rep(i,n)cd[i]=code[i]-'0';
		rep(i,n+1)rep(j,1<<3*(K-1))dp[i][j]=1;
		dp[0][0]=K;
		
		rep(i,1<<3*(K-1))for(int j=1;j<=K;j++){
			cost[i][j]=K;
			for(int k=K-1;k>=0;k--)if((i>>3*k&7)==j)cost[i][j]=k+1;
		}
		
		int mask=(1<<3*(K-1))-1;
		
		rep(i,n)rep(j,1<<3*(K-1)){
			if(cd[i]){
				int nj=j<<3&mask|cd[i],nc=min(dp[i][j],cost[j][cd[i]]);
				dp[i+1][nj]=max(dp[i+1][nj],nc);
			}
			else for(int d=1;d<=K;d++){
				int nj=j<<3&mask|d,nc=min(dp[i][j],cost[j][d]);
				dp[i+1][nj]=max(dp[i+1][nj],nc);
			}
		}
		int ans=1; rep(j,1<<3*(K-1))ans=max(ans,dp[n][j]);
		return ans;
	}
};