Codeforces #941 : Div1 C. Folding Strip

コードは短い。
https://codeforces.com/contest/1965/problem/C

問題

Nマスが並んだ紙があり、各マスは0/1が書かれている。
この上を、重なったマスが同じ数字となるように折ることができるとき、最小のマス数は何マスか。

解法

最終的に、0/1は連続しない。連続する場合、その間を折ることができる。
最終的に残る0/1の列の最小数は以下のように求められる。

A[i] := iが偶数の時、iマス目が0なら-1、1なら+1。iが奇数の時その逆。
とする数列を考える。この数列のprefix sumの最大値と最小値の差が解となる。

int T,N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		int L=0,R=0,cur=0;
		FORR(c,S) {
			if(c=='0') {
				if(cur%2==0) cur--;
				else cur++;
			}
			else {
				if(cur%2==0) cur++;
				else cur--;
			}
			L=min(L,cur);
			R=max(R,cur);
		}
		cout<<R-L<<endl;
		
	}
}

まとめ

実験で法則を見つけると実装は簡単。