kmjp's blog

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

Codeforces #313 Div1 B. Equivalent Strings

意外とTLEさせるのが難しい問題。
http://codeforces.com/contest/559/problem/B

問題

同じ長さの文字列A,Bは、以下の少なくとも片方を満たせば同等であると言える。

  • AとBが一致する。
  • A,Bの長さが偶数長の場合、以下の何れかが成り立つ。
    • Aの前半分とBの前半分が同等で、かつAの後ろ半分とBの後ろ半分が同等
    • Aの前半分とBの後ろ半分が同等で、かつAの前半分とBの後ろ半分が同等

2つの文字列S,Tが同等か答えよ。

解法

大きく2つの方針があるようだ。

  • 定義通り再帰する。途中適度に枝刈りをしないとTLEの可能性がある。
  • S,Tそれぞれ以下の最小化処理を再帰的に繰り返し、出来上がった文字列が一致するか判定する。
    • 文字列Aに対する最小化処理を以下のように定める。
      • Aが奇数長ならそのままAを返す。
      • Aが偶数長なら前半分と後ろ半分に分け、それぞれ最小化処理を行う。その後、最小化した2つの文字列を辞書順で小さい方を前にして連結して返す。

自分は後者で回答。
再帰ではなく、長さの短い順に前半後半を入れ替える処理を繰り返している。

int L,L2;
char S[2][202020];
char hoge[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S[0]>>S[1];
	L=strlen(S[0]);
	
	FOR(j,2) {
		L2=L;
		while(L2%2==0) L2/=2;
		for(L2;L2<L;L2*=2) {
			for(x=0;x<L;x+=2*L2) {
				if(strncmp(S[j]+x,S[j]+x+L2,L2)>0) {
					memmove(hoge,S[j]+x,L2);
					memmove(S[j]+x,S[j]+x+L2,L2);
					memmove(S[j]+x+L2,hoge,L2);
				}
			}
		}
	}
	
	cout << ((strncmp(S[0],S[1],L)==0)?"YES":"NO")<<endl;
	
}

まとめ

再帰で危なっかしいコードはいくつか見かけたが、TLEさせるInputを探すのが難しい。