AtCoder ARC #132 : D - Between Two Binary Strings

こっちは何とか解けた。
https://atcoder.jp/contests/arc132/tasks/arc132_d

問題

01で構成された2つの文字列S,Tが与えられる。
SとTは並べ替えると互いに一致する。

並べ替えて一致する2つの文字列A,Bにおいて、距離d(A,B)を、Aに隣接2要素のswapを繰り返してBにする最小swap回数と定義する。
また、文字列の美しさを、隣接する文字列が一致する箇所とする。

Uをd(S,U)+d(U,T)=d(S,T)を満たす文字列とするとき、美しさの最大値を求めよ。

解法

まず最初にSとTをチェックし、「何個目の0/1は、Uのうち何文字目から何文字目の間に入る必要があるか」を求めておこう。
Uとして0で始めるケースと1で始めるケースをはじめ、できるだけ貪欲に同じ文字を後ろにつけていけるかチェックしよう。
もし同じ文字を無理に同じにつけようとすると「何個目の0/1は、Uのうち何文字目から何文字目の間に入る必要があるか」の条件に違反する場合は、そこで0/1を切り替える。

int N,M;
string S,T;

vector<int> P[2][2];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>S>>T;
	
	FOR(i,N+M) {
		P[0][S[i]-'0'].push_back(i);
	}
	FOR(i,N+M) {
		P[1][T[i]-'0'].push_back(i);
	}
	
	int ma=0;
	FOR(i,2) {
		if(P[0][i].empty()) continue;
		if(P[0][i][0]&&P[1][i][0]) continue;
		int C[2]={0,0};
		int cur=i;
		C[cur]=1;
		int score=0;
		string G;
		G+='0'+i;
		for(int step=1;step<N+M;step++) {
			if(P[0][cur].size()==C[cur]) {
				cur^=1;
			}
			else if(P[0][cur^1].size()==C[cur^1]) {
				score++;
			}
			else if(min(P[0][cur][C[cur]],P[1][cur][C[cur]])<=step&&max(P[0][cur^1][C[cur^1]],P[1][cur^1][C[cur^1]])>step) {
				score++;
			}
			else {
				cur^=1;
			}
			G+='0'+cur;
			C[cur]++;
		}
		ma=max(ma,score);
	}
	
	cout<<ma<<endl;
	
}

まとめ

ちょっと手間取ったけど、WAは出さなかったし遅れまくったわけでもないのでまぁいいか。