Codeforces #193 Div2. E. Binary Key

ようやく最後のE。
http://codeforces.com/contest/332/problem/E

問題

文字列P,Sおよび整数Kが与えられる。

K文字の0,1で与えられる文字列Qがあるとする。
Pを無限回繰り返したPRとQを無限回繰り返したものQRを並べ、QR[i]が1となるiに対してPR[i]を抜き出して連結する、という処理をSと同じ長さ分集まるまで繰り返す。

この時連結後の文字列がSと一致するようなQを構築し、辞書順最小のものを答えよ。

解法

K文字中1の数がM個あると仮定し、それぞれ題意を満たすQを構築する。
Q[i]=1となるiがQ中j個目だとすると、P[i]=S[j]、P[i+K]=S[j+M]、P[i+2K]=S[j+2M]...を満たすはずなので、そのようなiをQの後ろから探していけばよい。
そのようなiをM個以上探せたら、そのQは解の候補となるので、そこから辞書順最小のものを選ぶ。
O(K*len(P)*len(S))の時間がかかるが、自分の場合1秒程度で解けている。

string P,S;
int K;
int OK[2001][201];

void solve() {
	int r,i,j,k,l,x,y,tx,ty;
	char hoge[20001];
	
	getline(cin,P);
	getline(cin,S);
	K=GETi();
	
	int rep=P.size()/K,rem=P.size()%K;
	if(rem==0) rep--,rem=K;
	string ret="Z";
	
	for(int a2=0;a2<=(K-rem)%K;a2++) {
		int a1=S.size()-a2*rep;
		if(a1%(rep+1)) continue;
		a1/=(rep+1);
		if(a1<0 || a1>rem) continue;
		FOR(x,K) FOR(y,a1+a2) {
			OK[x][y]=1;
			for(i=y,j=x;j<P.size() && i<S.size();j+=K,i+=a1+a2) if(P[j]!=S[i]) OK[x][y]=0;
		}
		string tt="";
		j=a2+a1;
		for(x=K-1;x>=0;x--) {
			if(j>0 && OK[x][j-1] && ((x>=rem && j>a1) || (x<rem && j<=a1))) tt+="1",j--;
			else tt+="0";
		}
		if(j==0) {
			reverse(tt.begin(),tt.end());
			ret=min(ret,tt);
		}
	}
	if(ret=="Z") ret="0";
	cout << ret << endl;
}

まとめ

最近Div2Eがノーヒントで解けることが増えてきた。よい傾向だ。