Codeforces #651 Div2 E. Binary Subsequence Rotation

Div2とはいえEの割に簡単。
https://codeforces.com/contest/1370/problem/E

問題

2つの文字列S,Tが与えられる。
両者01で構成され、それぞれの登場回数はSとTで等しい。

Sのうちいくつかのindexを指定し、その文字を1つrotateする、という処理を繰り返しSをTにしたい。
最小何回処理を行う必要があるか。

解法

Sのうち、S[i]!=T[i]であるような位置だけ抜き出した文字列Uを考える。
そうするとこの問題は、Uを101010...または010101...いくつに分解できるかという問題になる。

int N;
string S,T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S>>T;
	set<int> C[2];
	FOR(i,N) if(S[i]!=T[i]) C[S[i]=='0'].insert(i);
	
	if(C[0].size()!=C[1].size()) return _P("-1\n");
	int ret=0;
	while(C[0].size()) {
		x=*C[0].begin();
		y=*C[1].begin();
		if(x<y) {
			i=0;
		}
		else {
			i=1;
			x=y;
		}
		ret++;
		while(1) {
			auto it=C[i^1].lower_bound(x);
			if(it==C[i^1].end()) break;
			y=*it;
			C[i].erase(x);
			C[i^1].erase(y);
			auto it2=C[i].lower_bound(y);
			if(it2==C[i].end()) break;
			x=*it2;
		}
		
	}
	cout<<ret<<endl;
}

まとめ

本番6分で解いてるし、これDiv3でもいい問題なような。