CODE FESTIVAL 2017 qual B D. 101 to 010

CODE FESTIVAL 2017 qual B D. 101 to 010

D: 101 to 010 - CODE FESTIVAL 2017 qual B | AtCoder

感想

コンテスト中はあやふやな実装でバグらせた。
DEGwerさんの提出コードを見ると、驚くほどわかりやすく実装されていたのでさすがだと思った。左右端の処理もきれい。
考えていることをしっかり整理してコードに落とす力が足りていない。

解法

左から普通にDPをする。DPの更新は101となっている部分に到達した時に、左側と右側の$\ 1\ $の個数をみていくようなDPで構わない。一見すると$\ O(n^2)\ $に見えるが、よく考えると各$\ 1\ $は高々$\ 2\ $回しか見ないので、$\ O(n)\ $で高速に計算される。

実装

#include "bits/stdc++.h"
using namespace std;

int dp[505050];

int main() {
        int n; 
        scanf("%d", &n);
        string s; 
        cin >> s;
        s = "0" + s + "0";
        for (int i = 1; i < s.size() - 1; i ++) {
                dp[i + 1] = max(dp[i + 1], dp[i]);
                if (s[i - 1] == '1' && s[i] == '0' && s[i + 1] == '1') {
                        int prev = i - 1, next = i + 1;
                        while (s[prev] != '0') {
                                dp[i + 1] = max(dp[i + 1], dp[prev - 1] + (i - prev));
                                prev --;
                        }
                        while (s[next] != '0') {
                                dp[next] = max(dp[next], dp[i - 2] + (next - i));
                                next ++;
                        }
                }
        }
        printf("%d\n", dp[s.size() - 1]);
        return 0;
}