CODE FESTIVAL 2017 qual B,D: 101 to 010

http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_d

結局10111111...または111111...101となる文字列を見つける問題になるんですが、言い換えが甘くて場合分けをミスり、WAを量産しました。証明しながら解くことの重要性を感じた問題でした。

あとprevの情報を使うdpは覚えるものを複雑化するより、遷移を飛ばす感じにした方が実装楽そうですね。

int N;
string str;

int dp[MAX_N];
int nex[MAX_N];

void solve() {
	cin >> N >> str; str += "0";
	nex[N] = N;
	rer(i, N, 0) {
		if(str[i + 1] == '0') nex[i] = i + 1;
		else nex[i] = nex[i + 1];
		//debug(i, nex[i]);
	}
	rep(i, 0, N) {
		MAX(dp[i + 1], dp[i]);
		if(str[i] == '1') {
			if(nex[i] + 1 < N && str[nex[i] + 1] == '1') {
				MAX(dp[nex[i] + 2], dp[i] + nex[i] - i);
			}

			if(i + 1 < N && str[i + 1] == '0' && nex[i + 1] > i + 2) {
				MAX(dp[nex[i + 1]], dp[i] + nex[i + 1] - (i + 1) - 1);
				MAX(dp[nex[i + 1] - 1], dp[i] + nex[i + 1] - (i + 1) - 2);
			}
		}
	}
	cout << dp[N] << "\n";
}