CODE FESTIVAL 2017 Qual B : D - 101 to 010

考察も実装もちょっと手間取った。
http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_d

問題

01で構成された文字列が与えられる。
部分文字列が101となっている箇所を、010に置き換えるという処理を任意の順番で行えるとき、処理の最大実行回数を求めよ。

解法

0が２連続している箇所はそれ以上変わりようもない。また端の0も変わりようがない。
そこで、元の文字列を中に00を含まず両端が1となる部分列に分解しよう。
以後はそのような個々の部分列を対象とする。
この部分列は00を含まないので、まず0で分割し、ここの要素が1を何個連続しているかという配列を作る。

ここで、消え方について考察する。
101111というように101の左右どちらかに1が連続しているとき、101を010に変換することで1の多い側の分だけ処理を実行できる。
先ほど0で要素を分割したが、これは隣の要素の1を1個拝借することで自身の1を全部消せることになる。

この考察をもとにDPしていこう。
要素群について端からDPしていき、各要素の状態ごとに処理回数の最大値を求めていこう。
直前に処理した要素の状態は４通りある。

• 手前の要素から1を借りてすべて消した。
• 手前の要素を消すために1を1を貸したが、残りは残っている
• 次の要素を消すために右端の1を貸す。
• 手つかずで残っている。

1が1個しかない場合、左右両方に1を貸すことはできない点に留意。

int N;
string S;
int from[4];
int to[4];

ll hoge(string S) {
	vector<int> V;
	V.push_back(0);
	FORR(c,S) {
		if(c=='0') V.push_back(0);
		else V.back()++;
	}
	
	ZERO(from);
	for(int i=1;i<V.size();i++) {
		
		// 0-none 1-left 2-right 3-keep
		if(V[i]==1) {
			to[0]=max({from[0],from[1]+V[i-1]-1,from[2]+1,from[3]+V[i-1]});
			to[1]=max({from[0],from[1]+V[i-1]-1,from[3]+V[i-1]});
			to[2]=max({from[0],from[1],         from[2],from[3]});
		}
		else {
			to[0]=max({from[0],from[1]+V[i-1]-1,from[2]+V[i]});
			to[1]=max({from[0],from[1]+V[i-1]-1,from[3]+V[i-1]});
			to[2]=max({from[0],from[1]+V[i-1]-1,from[2]+V[i]-1,from[3]+V[i-1]});
		}
		to[3]=max({from[0],from[1],from[2],from[3]});
		
		
		swap(from,to);
	}
	int ret=max({from[0],from[1],from[2],from[3]});
	//cout<<S<<" "<<ret<<endl;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	N+=2;
	S+="00";
	ll ret=0;
	FOR(i,N) {
		if(S[i]=='0') continue;
		for(j=i+1;j<N;j++) {
			if(S[j]=='0' && S[j+1]=='0') {
				ret+=hoge(S.substr(i,j-i));
				i=j+1;
				break;
			}
		}
	}
	cout<<ret<<endl;
}

まとめ

状態遷移が混乱した。