TopCoder SRM 803 : Div1 Medium MarriageAndSelectionChallenge

無駄に面倒な問題…。
https://community.topcoder.com/stat?c=problem_statement&pm=16270&rd=18601

問題

最大12種類の文字で構成される文字列Sが与えられる。
Sの部分文字列のうち、同種の文字が連続しているような文字列Tのうち最長のものを求めよ。
同じ長さの候補が複数あるなら、辞書順最小のものを求めよ。

解法

まず最長のものを求めよう。
f(n,mask) := Sのn文字目を含み、またそれ以降で構成される部分文字列のうち、出てくる文字がmaskに示す内容であるもの
とする。
これをnの大きい順に埋めて行こう。
n文字目の次の文字12通りそれぞれについて最寄りのものを総当たりしておけばよい。

f(n,mask)が求まったら、これが最大となるものを求め、そこからDPの復元で文字列を再構成していく。

int nex[3030][12];
int dp[3030][1<<12];
int to[3030][1<<12];

class MarriageAndSelectionChallenge {
	public:
	string solve(string S) {
		int N=S.size();
		int i,j,mask;
		
		FORR(c,S) c-='a';
		FOR(i,12) nex[N][i]=N;
		FOR(i,1<<12) FOR(j,N+2) dp[j][i]=-1<<20;
		FOR(i,1<<12) dp[N][i]=0;
		
		MINUS(to);
		
		for(i=N-1;i>=0;i--) {
			FOR(j,12) nex[i][j]=nex[i+1][j];
			nex[i][S[i]]=i;
			
			FOR(j,12) {
				int t=nex[i+1][j];
				FOR(mask,1<<12) if(dp[t][mask]>=0) {
					if(S[i]!=j && mask&(1<<S[i])) continue;
					int nmask=mask|(1<<S[i]);
					if(dp[i][nmask]<dp[t][mask]+1) {
						dp[i][nmask]=dp[t][mask]+1;
						to[i][nmask]=j;
					}
				}
			}
		}
		
		int ma=-1;
		int cur=-1;
		FOR(i,N) if(dp[i][(1<<12)-1]>ma || (dp[i][(1<<12)-1]==ma && S[i]<S[cur])) {
			ma=dp[i][(1<<12)-1];
			cur=i;
		}
		
		string T;
		int c=cur;
		int m=(1<<12)-1;
		while(c<N) {
			T.push_back(S[c]+'a');
			i=to[c][m];
			if(S[c]!=i) m^=1<<S[c];
			c=nex[c+1][i];
		}
		
		return T;
		
		
	}
}

まとめ

本番もうちょいややこしいコード書いてたけど、なんとか通ってよかった。