AtCoder AGC #030 : E - Less than 3

考察はまだしも実装は容易。
https://atcoder.jp/contests/agc030/tasks/agc030_e

問題

0/1で構成される同じ長さNの文字列S,Tがある。
Sのうち1文字を0/1反転させる、という処理を繰り返しSをTにしたい。
ただし、その過程で0か1が3連続する箇所があってはならない。

最小処理回数を求めよ。

解法

3連続させられないということは、0と1の境目は文字列の端以外では生成・削除できないことを意味する。
境目を端以外で作成・削除しようと、000と010のような形を相互変換しなければならず、これは条件に反する。

境目の移動は任意で、処理1回で1動かせる。(011⇔001など)
３つ並ぶ瞬間がないよう順番さえ気にすれば、移動量は任意である。

ここから、SとTにおける0/1の境目を列挙し、どの境目がどの境目に移動する、という条件を総当たりして、境目の移動階数の総和を求め、その最小値を答えればよい。

int N;
string S,T;

vector<int> A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S>>T;
	
	if(N<3) {
		int ret=0;
		FOR(i,N) ret+=S[i]!=T[i];
		cout<<ret<<endl;
		return;
	}
	
	if(S[0]=='1') A.push_back(0);
	if(T[0]=='1') B.push_back(0);
	for(i=1;i<N;i++) {
		if(S[i]!=S[i-1]) A.push_back(i);
		if(T[i]!=T[i-1]) B.push_back(i);
	}
	
	int mi=1<<30;
	for(int D=-(N+2);D<=N+2;D++) if(D%2==0) {
		int tot=0;
		FOR(i,A.size()) {
			y=i+D;
			if(y<0) r=0;
			else if(y>=B.size()) r=N;
			else r=B[y];
			tot+=abs(A[i]-r);
		}
		FOR(i,B.size()) {
			y=i-D;
			if(y>=0 && y<A.size()) continue;
			if(y<0) r=0;
			else r=N;
			tot+=abs(B[i]-r);
		}
		
		mi=min(mi,tot);
	}
	
	cout<<mi<<endl;
	
}

まとめ

1400ptの割に簡単？
まぁ考察を先見ちゃってるからかもな…。