微妙に面倒。さらにコーナー。

problem

0 1の列が与えられる。高々$1$回のswapをして、連続する0の数を最大化せよ。

solution

0 の列が間にちょうどひとつの1を挟んで隣接しているなら併合できる。 そんな感じで探す。ただし000001や111001000111のような1を飛ばす先が足りてないケースに注意する。 $O(N)$。

implementation

#!/usr/bin/env python3
def solve(s):
    result = 0
    last_l, last_r = (-3, -2)
    l = 0
    while l < len(s):
        while l < len(s) and s[l] == '1':
            l += 1
        if l == len(s):
            break
        r = l + 1
        while r < len(s) and s[r] == '0':
            r += 1
        result = max(result, r - l + 1)
        if last_r + 1 == l:
            result = max(result, r - last_l)
        last_l, last_r = (l, r)
        l = r
    result = min(s.count('0'), result)
    return result
print(solve(input()))