kmjp's blog

競技プログラミング参加記です

Yosupo Wettbewerb : C : Palindrome Relinquish

TLE対策に手間取った。
http://kcs.miz-miz.biz/contest/1027/view/C

問題

超回文とは以下のように再帰的に定義される。

  • 1文字の文字列は超回文である。
  • 奇数長の回文であり、真ん中の文字により分断された左右の文字列も超回文であるものは超回文である。

0-9で構成されるN文字の文字列Sがある。
この文字列の部分文字列中に、K文字の超回文があるか答えよ。

解法

超回文の定義より、K=2^H-1の形で表せるものしか超回文になりえない。
Kの制限より、Hは高々6である。

よって超回文となりえる文字列Tは高々10^6通り。
S中にTが含まれるかは、前処理として「次に登場する0~9の位置」を求めておけばO(T)で求められるので、全体で63*10^6程度のループ回数で終わる。
…というのが想定解。

自分は別解法で行った。
Sの前から超回文の候補を探索するとき、Tのうち1,2,4,8...文字目は新規に文字列を選ぶタイミングであり、それ以外の3,5,6,7,9,...文字目は過去に選んだ文字と同じ番号か来なければならない。

よって1,2,4,8...文字目の時は0~9を総当たりして、それぞれ次に来る0~9を選ぶ。
3,5,6,7,9...文字目の時は、過去登場済みと同じものを選ぶ。
というようにDFSする。
計算量は結局同じ。

int N,K,H;

int L[1001],LF[1001];
int nex[1001][10],val[10];
string S;

void dfs(int cur,int X,ll T) {
	int x;
	if(X>K) {
		_P("Found\n");
		exit(0);
	}
	if(cur>=N) return;
	if(N-cur<K-X-1) return;
	
	if(LF[L[X]]==X) {
		FOR(x,10) if(nex[cur][x]<N) dfs(nex[cur][x]+1,X+1, T | (((ll)x)<<(L[X]*4)));
	}
	else {
		int t=((T>>(L[X]*4))&15);
		if(nex[cur][t]<N) dfs(nex[cur][t]+1,X+1,T);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	if((K&(K+1))!=0) return _P("Not Found\n");
	while(1<<(H+1) <= K) H++;
	
	FOR(i,10) val[i]=N;
	for(i=N-1;i>=0;i--) {
		val[S[i]-'0']=i;
		FOR(j,10) nex[i][j]=val[j];
	}
	
	FOR(i,K) {
		x=i+1;
		while(x%2==0) L[i+1]++, x/=2;
		if(LF[L[i+1]]==0) LF[L[i+1]]=i+1;
	}
	
	dfs(0,1,0);
	_P("Not Found\n");
}

まとめ

面白い問題でした。
これいつか他の場所で出てきそう。