yukicoder : No.2018 X-Y-X

コードは短い。
https://yukicoder.me/problems/no/2018

問題

ABで構成された文字列S,Tが与えられる。
S[i]=S[i+2]の時、S[i+1]をS[i]にできるとする。
S=Tとすることが可能か。可能なら最小操作回数を求めよ。

解法

まずSの先頭と末尾はいじれないので、SとTの先頭と末尾が一緒かは確認しておこう。
S'[i]=S[i+1] xor S[i]
T'[i]=T[i+1] xor T[i]
として、隣接要素のdiffを取ってみる。
この時、文字列に対する操作は、S'中で同じ値が2個連続するとき、両者01反転させることを意味する。

そこで、S'',T''をS',T'において偶数番目の要素を01反転した数列とする。
すると、S中の処理は、S''で隣接する01をswapする処理となる。
あとはS''とT''中の1の数を数え、一致する場合はindexの差の総和を取ろう。

int N;
string S,T;
int A[202020];
int B[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S>>T;
	if(S[0]!=T[0]||S[N-1]!=T[N-1]) {
		cout<<-1<<endl;
		return;
	}
	vector<int> X,Y;
	FOR(i,N-1) {
		A[i]=(S[i]!=S[i+1])^(i%2);
		B[i]=(T[i]!=T[i+1])^(i%2);
		if(A[i]) X.push_back(i);
		if(B[i]) Y.push_back(i);
	}
	if(X.size()!=Y.size()) {
		cout<<-1<<endl;
	}
	else {
		ll ret=0;
		FOR(i,X.size()) ret+=abs(X[i]-Y[i]);
		cout<<ret<<endl;
	}
		
		
}

まとめ

diffを取るのも、偶数位置を反転するもの定番テクではあるけど、文字列の操作からここに持ってこれるのは面白いな。