4か月以上ぶりにCodeforcesのこと書く。
http://codeforces.com/contest/1381/problem/A2
問題
01で構成されたN文字の文字列A,Bが与えられる。
Aのprefixを選択し、0/1反転しつつ並びも反転する処理を2N回まで行えるとする。
A=Bとなるような反転位置を求めよ。
解法
Aを後ろからそろえていくことを考える。
今A[i]!=B[i]とする。
- A[0]!=B[i]なら、[0,i]を指定すればA[i]=B[i]となる。
- A[0]==B[i]なら、[0,0]を指定後、[0,i]を指定すればA[i]=B[i]となる。
上記処理は愚直に行うとO(N^2)かかるが、A[0...i]にあるのはAの初期状態のどこに該当するか、加えてその区間の反転回数の偶奇を覚えておけば、反転処理はO(1)で行えるので全体でO(N)で済む。
int H; int N; string S,T; void solve() { int i,j,k,l,r,x,y; string s; cin>>H; while(H--) { cin>>N>>S>>T; int L=0,R=N-1,F=0; vector<int> V; for(i=N-1;i>=0;i--) { if((S[R]^F)!=T[i]) { if((S[L]^F)==T[i]) V.push_back(1); V.push_back(abs(R-L)+1); swap(L,R); F^=1; } if(L<=R) R--; else R++; } cout<<V.size(); FORR(v,V) cout<<" "<<v; cout<<endl; } }
まとめ
頑張って追いかけるか…。
1年以上前なのであまり記憶にないな。