kmjp's blog

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

Codeforces #658 Div1 A2. Prefix Flip (Hard Version)

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年以上前なのであまり記憶にないな。