101 to 010 [CODE FESTIVAL 2017 予選B D]

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

解法

http://code-festival-2017-qualb.contest.atcoder.jp/submissions/1673613

DPで解く
dp[i] := i文字目までの操作の最大回数
公式解説にもあるが、問題をすり替えると『Sから重ならないよい部分文字列を選んでそのコストの和を最大化する問題』となる。
「11...1101」と「1011...11」を選択していくことになる。
　
DPを作る前に

• nxt[i] := 次に0が来るインデックス
• bak[i] := 前に0が来るインデックス

を作っておくとO(1)で更新できる
　
後は普通に実装するだけなのだが、ミスってしょうがなかったので、どういうミスだったか紹介しておく。
一般的なDPはdp[i]からdp[i+j]を更新する(配るDP)か、dp[i]の更新にdp[i-j]を使う(貰うDP)かをやる。
今回のDPをその2つを組み合わせる必要がある。

dp[i]を更新するのに、「11...1101」は配るDPをやる。
これは貰うDPをやると、「1111101」という文字列があった時に「101」「1101」「11101」「111101」「1111101」から持ってくる必要がある（どれが最適な怪しいため）。
しかし、配るDPとすると、次の「01」となる部分までで一意に遷移が定まる。
同様に、dp[i]を更新するのに、「1011...11」は貰うDPをやる。
　
これを頑張ると答え。

int N;
string S;
int dp[501010];
//---------------------------------------------------------------------------------------------------
int nxt[501010], bak[501010];
void _main() {
    cin >> N >> S;
    S += "#";
 
    int bk = -1;
    rep(i, 0, N) {
        bak[i] = bk;
        if (S[i] == '0') bk = i;
    }
 
    int nx = N;
    rrep(i, N - 1, 0) {
        nxt[i] = nx;
        if (S[i] == '0') nx = i;
    }
 
    rep(i, 0, N) {
        dp[i + 1] = max(dp[i + 1], dp[i]);
 
        // 1011111...
        if (S[i] == '1') {
            if (1 <= bak[i] && S[bak[i] - 1] == '1') {
                int c = i - bak[i];
                dp[i + 1] = max(dp[i + 1], dp[bak[i] - 1] + c);
            }
        }
 
        if (S[i] == '1') {
            // ...1111101
            if (nxt[i] < N - 1 && S[nxt[i] + 1] == '1') {
                int c = nxt[i] - i;
                dp[nxt[i] + 2] = max(dp[nxt[i] + 2], dp[i] + c);
            }
        }
    }
 
    cout << dp[N] << endl;
}