意外と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つの文字列を辞書順で小さい方を前にして連結して返す。
- 文字列Aに対する最小化処理を以下のように定める。
自分は後者で回答。
再帰ではなく、長さの短い順に前半後半を入れ替える処理を繰り返している。
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を探すのが難しい。