AtCoder ARC #207 (AtCoder Japan Open -予選-) : E - Erase and Append

意外とコード量増えた。
https://atcoder.jp/contests/arc207/tasks/arc207_e

問題

N文字のバイナリ文字列S,Tが与えられる。
Sの隣接する2文字を選択し、片方を複製してSの末尾に加えつつ、もう片方を削除することを繰り返す。
S=Tとすることができるか、できるなら一例を示せ。

解法

まずコーナーケースを除く。

• 最初からS=Tの場合の場合は0手で可。
• N=2の時は、あり得る操作を総当たりする。
• Tに含まれる文字で、Sにないものがあれば不可。
• Tが最後の1文字だけ異なるとき不可。

それ以外のケースを考える。
まず0手又は1手使い、S[0]!=S[N-1]の状態にする。
あとは、S[0]またはS[N-1]を残すようにし、Sの末尾にT[1...(N-2)]ができた状態にする。
するとS[0]!=S[1]なので、T[0]と一致する方を残そう。
そうするとSとTの先頭(N-1)文字が一致する。あとは必要に応じ末尾をそろえるとよい。

int N,T;
string A,B;
int C[2][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>A>>B;
		ZERO(C);
		if(A==B) {
			cout<<0<<endl;
			continue;
		}
		if(N==2) {
			if(A[0]==B[0]&&A[0]==B[1]) {
				cout<<1<<endl;
				cout<<"1 2"<<endl;
			}
			else if(A[1]==B[0]&&A[1]==B[1]) {
				cout<<1<<endl;
				cout<<"2 1"<<endl;
			}
			else {
				cout<<-1<<endl;
			}
			continue;
		}
		
		FORR(c,A) C[0][c-'0']++;
		FORR(c,B) C[1][c-'0']++;
		if(C[1][0]&&C[0][0]==0||C[1][1]&&C[0][1]==0) {
			cout<<-1<<endl;
			continue;
		}
		if(C[1][B.back()-'0']==1) {
			cout<<-1<<endl;
			continue;
		}
		vector<pair<int,int>> V;
		
		if(A[0]==A.back()) {
			FOR(i,N-1) if(A[i+1]!=A[0]) {
				if(i) {
					V.push_back({i+1,i});
					A=A.substr(0,i)+A.substr(i+1)+A.substr(i+1,1);
				}
				else {
					V.push_back({i+1,i+2});
					A=A.substr(0,i+2)+A.substr(i+3)+A.substr(i+1,1);
				}
				break;
			}
			assert(A[0]!=A.back());
		}
		assert(A.size()==N);
		for(i=1;i<N-1;i++) {
			if(B[i]==A[0]) {
				V.push_back({0,1});
			}
			else {
				V.push_back({N-i,N-1-i});
			}
		}
		A=A.substr(0,1)+A.substr(N-1,1)+B.substr(1,N-2);
		if(B[0]==A[0]) {
			V.push_back({0,1});
			A=A.substr(0,1)+B.substr(1,N-2)+A.substr(0,1);
		}
		else {
			V.push_back({1,0});
			A=A.substr(1,1)+B.substr(1,N-2)+A.substr(1,1);
		}
		if(A.back()!=B.back()) {
			for(i=N-2;i>=0;i--) if(A[i]==B[N-1]) {
				V.push_back({i,i+1});
				A=A.substr(0,i+1)+A.substr(i+2)+A.substr(i,1);
				break;
			}
		}
		cout<<V.size()<<endl;
		FORR2(a,b,V) cout<<a+1<<" "<<b+1<<endl;
	}
}

まとめ

意外にシンプルな解法。