TopCoder SRM 837 : Div1 Hard ConcatGame

考えはあっていたのだが。
https://community.topcoder.com/stat?c=problem_statement&pm=17814

問題

アルファベット小文字からなる文字列の大小順を、以下のように定義する。

• 文字数が少ない文字列ほど小さい。
• 文字数が同じ文字列の大小は、辞書順に従う。

整数列X[i]が与えられる。各X[i]は、上記定義による文字列のうち、小さい順からX[i]番目までのいずれかの文字列を選べることを意味する。
まず、X[i]に対し対応する文字列を1つずつ選び、それをある順で連結したところ、その結果はCとなった。

この結果に対し、以下のいずれであるか答えよ。

• Cとなる文字列の選びかた・連結順は存在しない
• Cとなる文字列の選びかた・連結順は存在する
  • 連結順のうち、Cは辞書順で最大で確定する
  • 連結順のうち、Cは辞書順で最大ではないことで確定する
  • 連結順のうち、Cは辞書順で最大かもしれないし最大ではないかもしれない

解法

BitDPで解く。
最大云々のところは、文字列を連結していく際、必ず降順に連結するなら、最大で確定、1か所でも降順が崩れる箇所があるなら最大てないことで確定する。
また文字列の選び方によっては、両方あり得ることもある。

f(n,mask,l) := Cの先頭n文字を、maskに示す文字列の部分集合の連結で表現し、かつ最後の文字列がl文字とする。この時、ここまでが常に降順である連結法の有無を示す真偽値
g(n,mask,l) := Cの先頭n文字を、maskに示す文字列の部分集合の連結で表現し、かつ最後の文字列がl文字とする。この時、ここまでで降順でない箇所を含む連結法の有無を示す真偽値

f(0,0,0)=Trueから始め、BitDPの要領で続く何文字かを選ぶパターンを総当たりしよう。
全文字列を連結した状態に相当するビットマスクをmとしたとき、f(|C|,m,*)のうち1つでもTrueがあればCが辞書順最大のケースが1個以上あり、g(|C|,m,*)のうち1個でもTrueがあればCが辞書順最大ではないケースが1個以上あることがわかる。

この処理の注意点で、文字列比較は重いので何度も行わないようにしよう。

ll N[10];

int len[13];
string S[13];

int dp[66][6][1<<13];

int cmp[66][66][66];

class ConcatGame {
	public:
	string analyze(vector <int> upperBounds, string claim) {
		N[0]=1;
		int i,j;
		ll sum=0;
		for(i=1;i<=6;i++) {
			N[i]=N[i-1]*26;
			sum+=N[i];
		}
		int M=upperBounds.size();
		FOR(i,M) {
			len[i]=1;
			int x=upperBounds[i];
			while(N[len[i]]<x) {
				x-=N[len[i]];
				len[i]++;
			}
			S[i]="";
			x--;
			FOR(j,len[i]) {
				S[i]+='a'+(x%26);
				x/=26;
			}
			reverse(ALL(S[i]));
		}
		
		int C=claim.size();
		if(C>65) return "lie";
		
		int a,b,c,d;
		FOR(a,C) for(b=0;a+b<=C;b++) {
			string s=claim.substr(a,b);
			for(c=0;a+b+c<=C;c++) {
				string t=claim.substr(a+b,c);
				cmp[a][b][c]=s+t<t+s;
			}
		}
		
		ZERO(dp);
		dp[0][0][0]=1;
		for(int cur=0;cur<C;cur++) {
			for(int plen=0;plen<=5;plen++) {
				if(plen>cur) continue;
				for(int mask=0;mask<1<<M;mask++) if(dp[cur][plen][mask]) {
					for(j=1;j<=5;j++) {
						if(cur+j>C) continue;
						string now=claim.substr(cur,j);
						FOR(i,M) if((mask&(1<<i))==0) {
							if(j>len[i]||(j==len[i]&&now>S[i])) continue;
							if(cmp[cur-plen][plen][j]) {
								dp[cur+j][j][mask|(1<<i)]|=2;
							}
							else {
								dp[cur+j][j][mask|(1<<i)]|=dp[cur][plen][mask];
							}
						}
					}
				}
			}
		}
		
		int pat=0;
		for(int plen=0;plen<=5;plen++) pat|=dp[C][plen][(1<<M)-1];
		cout<<pat<<endl;
		if(pat==0) return "lie";
		if(pat==1) return "good";
		if(pat==2) return "bad";
		if(pat==3) return "unknown";
	}
}

まとめ

次回は無事開催できるといいね。