Code Festival 2017 予選B D - 101 to 010

問題

0と1のみからなる文字列sが与えられる
この文字列に対し、「"101"となっているところを"010"に書き換える」という操作を行うことができる
最大で何回操作を行えるか

1 <= |s| <= 5*10^5

解法

操作を逆から見ると、最終状態の1は「もともと1だった」か「101に操作をして出来た」かのどっちかである
すると最終状態での1個の1に対応するのは初期状態における
type-a) 1
type-b) 10111...111 (右側で1がk個連続するならk回操作ができる)
type-c) 111...11101 (同様)
のどれか
つまりtype-bやtype-cをうまく作りながらsを分割して答えを最大化することを考えればいい

dp[i]: i文字目までの答え
l[i]: i文字目より左にある'0'のうち最も右にあるもののインデックス
r[i]: i文字目より右にある'0'のうち最も左にあるもののインデックス
としてsを左から1文字ずつ見ていくと、dpの遷移は
1) i文字目をtype-bの右端とする場合
2) i文字目をtype-cの左端とする場合
の2通りを考えればいい
前者はもらうDP、後者は配るDPになる

int n, l[500500], r[500500], dp[500500];
string s;

signed main() {
	cin >> n >> s;
	int t = -1;
	rep(i,n) {
		l[i] = t;
		if (s[i]=='0') t = i;
	}
	t = n;
	for (int i=n-1; i>=0; i--) {
		r[i] = t;
		if (s[i]=='0') t = i;
	}
	rep(i,n) {
		chmax(dp[i+1], dp[i]);
		if (s[i]=='0') continue;
		// 1011111
		if (1<=l[i] && s[l[i]-1]=='1') chmax(dp[i+1], dp[l[i]-1] + i-l[i]);
		// 1111101
		if (r[i]<n-1 && s[r[i]+1]=='1') chmax(dp[r[i]+2], dp[i] + r[i]-i);
	}
	cout << dp[n] << endl;
}

ちょうど1年くらい前、競プロやりだしてすぐのときにこの問題に遭遇して何もわからなくて「こんな意味不明な問題解けるやつバケモンか?」って思った記憶がある
今実際に解けてるわけでちょっと感慨深い