Codeforces #1075 : Div2 E. Majority Wins?

Codeforcesはたまにこういう問題出るな。
https://codeforces.com/contest/2189/problem/E

問題

バイナリ文字列Sが与えられる。
Sの部分文字列を選び、最多頻度の１文字で置き換える処理を行い、S="1"としたい。
その際、長さの減少分+1のコストがかかる。
可能なら、最小コストを答えよ。

解法

「長さの減少分+1のコスト」というが、全体から元の文字列の長さを引くと、(処理回数+1)なので、処理回数を減らす問題となる。
"1"が1個でもあるなら、最大でも4手で達成できる。
xxxxx1yyyyyyの形があるなら、２手でx1yに持ち込め、あと２手で1にできる。
あとは細かく場合分けして、0～3手で済む場合を求めよう。

int T;
int N;
string S;
int sum[1002020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		
		//0手
		if(S=="1") {
			cout<<N-1<<endl;
			continue;
		}
		int C[2]={};
		FORR(c,S) C[c-'0']++;
		if(C[1]==0) {
			cout<<-1<<endl;
			continue;
		}
		//1手
		if(C[0]<=C[1]) {
			cout<<N<<endl;
			continue;
		}
		FOR(i,N) {
			sum[i+1]=sum[i]+(S[i]=='1')-(S[i]=='0');
		}
		//2手
		if(2*C[1]-N==-1) {
			cout<<N+1<<endl;
			continue;
		}
		//prefixかsuffixが超過
		FOR(i,N) {
			if(sum[i+1]>0||sum[N]-sum[i]>0) break;
		}
		if(i<N) {
			cout<<N+1<<endl;
			continue;
		}
		//3手
		//prefixかsuffixが超過
		FOR(i,N) {
			if(sum[i+1]>=0||sum[N]-sum[i]>=0) break;
		}
		if(i<N) {
			cout<<N+2<<endl;
			continue;
		}
		FOR(i,N-1) if(S[i]=='1'&&S[i+1]=='1') break;
		if(i<N-1) {
			cout<<N+2<<endl;
			continue;
		}
		cout<<N+3<<endl;
	}
}

まとめ

一見O(N)ぐらいの手数が必要そうで、結局定数回の手数で行けるやつ。
コストの式は定数回で済むことを悟られないようカモフラージュを狙ったのかな。