TopCoderOpen 2017 Round2C Hard TreasureOfWinedag

うーん、あと一歩。
https://community.topcoder.com/stat?c=problem_statement&pm=14648

問題

アルファベット小文字で構成されるN文字の文字列Tが与えられる。
これをK個の連続部分文字列に分解したい。

文字列のコストとは、そこに含まれる文字の種類数と定義する。
分割後の各部分文字列のコストの総和の最小値を求めよ。

解法

W=文字の種類(今回は26)とする。どんなに長い文字列でもコストの最大値はWであるから、この問題の解はK～(K+25)の範囲に収まる。
このことを利用しよう。

以下をDPで求める。
f(i,j) := Tのprefix f(i,j)文字をi個に分割したとき、コストの総和がi+jとなる最大値

f(i,j) (i≦K)を求めれば、解はK+jの最小値となる。
同じ文字が続く場合など、K個未満に分割した方がコストが小さくなる場合もあるが、この問題はK個ちょうどに分割しなければならないため、解は(i+j)ではなく(K+j)となる。

f(i,j)がわかっているとき、(i+1)個目の分割文字列の取り方は、コストが1～26の26通りの最長部分文字列だけ考えればいいので、この問題は前処理も含めO(NWlogW+KW^2)で解ける。

int nex[101010][27];
int dp[101010][27];

class TreasureOfWinedag {
	public:
	int solvePuzzle(int N, int K, int m, int c0, vector <int> c1, vector <int> c2, vector <int> c3, vector <int> c4, string s) {
		int i,j,k;
		for(i=s.size();i<N;i++) {
			ll t=i*(ll)c0%m;
			char nc='z';
			FOR(j,25) {
				if(t>=c3[j]&&t<=c4[j]&&((t%c1[j])==c2[j])) {
					nc='a'+j;
					break;
				}
			}
			s+=nc;
		}
		ZERO(nex);
		
		FOR(j,26) nex[N][j]=N;
		for(i=N-1;i>=0;i--) {
			FOR(j,26) nex[i][j]=nex[i+1][j];
			nex[i][s[i]-'a']=i;
		}
		FOR(i,N) sort(nex[i],nex[i]+26);
		MINUS(dp);
		dp[0][0]=0;
		dp[K][25]=N;
		
		FOR(i,K) {
			FOR(j,26) {
				if(dp[i][j]>=N || dp[i][j]<0) continue;
				for(k=0;j+k<=25;k++) dp[i+1][j+k]=max(dp[i+1][j+k], nex[dp[i][j]][k+1]);
			}
		}
		
		int mi=K+25;
		FOR(i,K+1) FOR(j,26) if(dp[i][j]>=N) mi=min(mi,K+j);
		
		return mi;
	}
}

まとめ

解の範囲が狭いことには気が付きつつも、そこからうまく探索範囲を限定できなかった。