Problem:


Score : 800 points

Problem Statement

Given is a string S, where each character is 0, 1, or ?.

Consider making a string S' by replacing each occurrence of ? with 0 or 1 (we can choose the character for each ? independently).
Let us define the unbalancedness of S' as follows:

(The unbalancedness of S') = \max \{ The absolute difference between the number of occurrences of 0 and 1 between the l-th and r-th character of S (inclusive) :\ 1 \leq l \leq r \leq |S|\}

Find the minimum possible unbalancedness of S'.

Constraints

1 \leq |S| \leq 10^6

Each character of S is 0, 1, or ?.

Input

Input is given from Standard Input in the following format:

S

Output

Print the minimum possible unbalancedness of S'.

Sample Input 1

0??

Sample Output 1

1

We can make S'= 010 and achieve the minimum possible unbalancedness of 1.

Sample Input 2

0??0

Sample Output 2

2

Sample Input 3

??00????0??0????0?0??00??1???11?1?1???1?11?111???1

Sample Output 3

4



Sample input:
0??


Sample output:
1

Submission status: Wrong Answer

Solution code:
s=input()
qus=s.count("?")
zeros=s.count("0")
ones=s.count("1")
result=abs(zeros-ones)
if qus%2 ==1:
  result+= -1
max1=1
max2=0
last=""
for subs in s:
  if subs == "?":
    continue
  if last == subs:
    max1+=1
  else:
    max1=1
    last=subs
  max2=max(max1,max2)
result=max(result,max2)
print(result)

Submission status: Wrong Answer

Solution code:
def check_first_num(S):
    for s in S:
        if s != '?':
            return s
    return '0'

s = input()
n = len(s)

left = 0
right = n
while right > left + 1:
    opt = (left + right) // 2
    determined = 0
    tmp = 0  # 0の個数 - 1の個数
    for i in range(n):
        if s[i] != '?' and determined == 0:
            determined = 1
        if not determined:
            continue

        if s[i] == '0': tmp += 1
        elif s[i] == '1': tmp -= 1
        else:
            if tmp > 0: tmp -= 1
            else: tmp += 1
        
        if abs(tmp) > opt:
            break
    else:
        right = opt
        continue
    left = opt

print(right)

Submission status: Wrong Answer

Solution code:
s=list(input())
zero=s.count('0')
iti=s.count('1')
hatena=s.count('?')
print(abs(zero-iti))

Submission status: Wrong Answer

Solution code:
S = map(str,input())
S ="".join(S)
lists = list(S)
n = 0
for i in lists:
    if i == "0":
        n +=1
print(n)

Submission status: Wrong Answer

Solution code:
S =  input()


def check(S):
    j = 0
    diff = []
    for ltr in S:
        if ltr == '?':
            j += 1
        else:
            if j not in diff:    
                diff.append(j)
            j = 0

    return max(diff)

Submission status: Wrong Answer

Solution code:
s=input()
qus=s.count("?")
zeros=s.count("0")
ones=s.count("1")
result=abs(zeros-ones)
if qus%2 ==1:
  result+= -1
print(result)

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)

left = 0
right = n
while right > left + 1:
    opt = (left + right) // 2
    tmp = 0  # 0の個数 - 1の個数
    for i in range(n):
        if s[i] == '0': tmp += 1
        elif s[i] == '1': tmp -= 1
        else:
            if tmp > 0: tmp -= 1
            else: tmp += 1
        
        if abs(tmp) > opt:
            break
    else:
        right = opt
        continue
    left = opt

print(right)

Submission status: Wrong Answer

Solution code:
s=input()
qus=s.count("?")
zeros=s.count("0")
ones=s.count("1")
result=abs(zeros-ones)
if qus ==1:
  if result>1:
    result+=-1
else:
  result+=qus%2
print(result)

Submission status: Wrong Answer

Solution code:
a = input()
b = []
c= []
for i in range(0, len(a)):
    if a[i]== "1":
        b.append("1")
    elif a[i]== "0":
        c.append("0")
print(abs(len(b)-len(c)))

Submission status: Wrong Answer

Solution code:
s=input()
qus=s.count("?")
zeros=s.count("0")
ones=s.count("1")
result=abs(zeros-ones)
result+=qus%2
print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys, io, os, re
import bisect
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]

def ldec(A, d=1): return map(lambda x: x - d, A)

S = s1()

def f(S, N, n):
    (L, U) = (n, n)

    for i in range(len(S)):
        #print(N, n, i, L, U)

        if S[i] == "0":
            U -= 1
            L -= 1
            if L < 0:
                L += 2
                if L > U:
                    return -1
        
        if S[i] == "1":
            U += 1
            L += 1
            if U > N:
                U -= 2
                if L > U:
                    return 1

        if S[i] == "?":
            U += 1
            L -= 1
            if U > N: 
                U -= 2
                if L > U:
                    return 1
            if L < 0: 
                L += 2
                if L > U:
                    return -1


    return 0

def solve(S, N):
    (lower, upper) = (0, N)

    while lower <= upper:
        n = (lower + upper) // 2
        t = f(S, N, n)
        #print("{} = f(S, {}, {})".format(t, N, n))

        if lower < upper:
            if t == 1:
                upper = n
            if t == -1:
                lower = n + 1
            if t == 0:
                return True
        else:
            if t == 0:
                return True
            else:
                return False

for N in range(len(S) + 1, -1, -1):
    if not solve(S, N):
        print(N + 1)
        break

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    d = {0: 0}
    for i in s:
        d2 = dict()

        for j in d.keys():
            k = d[j]
            if i != "1":
                temp = max(j-1, 0)
                if temp not in d2:
                    d2[temp] = [k-1]
                else:
                    d2[temp].append(k-1)
            if i != "0":
                if j+1 not in d2:
                    d2[j+1] = [min(0, k+1)]
                else:
                    d2[temp].append(min(0, k+1))

        d = dict()
        for j in d2.keys():
            d[j] = max(d2[j])

        for i in d2.keys():
            if i-1 in d:
                if d[i] == d[i-1]:
                    d.pop(i)
                    continue
            if i-2 in d:
                if d[i] == d[i-2]:
                    d.pop(i)

    ans2 = 10**10
    for i, j in d.items():
        ans2 = min(ans2, i-j)
    print(ans2)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    m = 1
    t = [None]*m
    t[0] = 0
    for i in s:
        t2 = [[] for _ in [0]*m]
        for j in range(m):
            k = t[j]
            if k is None:
                continue
            if i != "1":
                t2[max(j-1, 0)].append(k-1)
            if i != "0":
                if j+1 < m:
                    t2[j+1].append(min(0, k+1))
                else:
                    t2.append([min(0, k+1)])
                    t.append(None)
                    m += 1
        for j in range(m):
            if t2[j]:
                t[j] = max(t2[j])
            else:
                t[j] = None
        for i in range(m-1, 1, -1):
            if t[i] == t[i-1]:
                t[i] = None
            if t[i] == t[i-2]:
                t[i] = None
        for i in range(m-1, -1, -1):
            if t[i] is None:
                t.pop()
                m -= 1
            else:
                break

    ans = 10**10
    for i in range(m):
        if t[i] is not None:
            ans = min(ans, i-t[i])
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
S = input()

L = 0
U = len(S)

while U - L > 1:
    M = (U + L) // 2

    OK = False
    for i in range(2):
        A = i
        B = M
        if A % 2 != B % 2: B -= 1

        NG = False
        for s in S:
            if s == '0':
                A -= 1
                B -= 1
            elif s == '1':
                A += 1
                B += 1
            else:
                A -= 1
                B += 1

            if A < 0: A += 2
            if B > M: B -= 2
            if A > B:
                NG = True
                break

        if not NG:
            OK = True
            break

    if OK:
        U = M
    else:
        L = M

print(U)

Submission status: Time Limit Exceeded

Solution code:
def check(s, m, parity):
    lo = parity
    hi = m - (m - parity) % 2

    for c in s:
        if c == '0':
            lo += 1
            hi += 1
        elif c == '1':
            lo -= 1
            hi -= 1
        else:
            lo -= 1
            hi += 1

        if lo < 0:
            lo += 2
        if hi > m:
            hi -= 2

        if lo > hi:
            return False

    return True


s = input()
l, r = 0, len(s)
while l + 1 < r:
    m = (l + r) // 2
    if check(s, m, 0) or check(s, m, 1):
        r = m
    else:
        l = m
print(r)

Submission status: Time Limit Exceeded

Solution code:
s = list(map(lambda x: -1 if x == '?' else int(x), input()))

def test(c):
    # current point can be seen as xth smallest val, where x can be any value in [a, b] (subset of [0, c])
    # a <= b
    a, b = 0, c
    ok = True
    discrete = False # when True x = a, a+2, ..., b-2, b
    for si in s:
        if si == 1:
            if a == b == c:
                return False
            a += 1
            b += 1
            if b > c:
                b = c - 1 if discrete else c
        elif si == 0:
            if a == b == 0:
                return False
            a -= 1
            b -= 1
            if a < 0:
                a = 1 if discrete else 0
        else:
            if a == b == 0:
                a = b = 1
            elif a == b == c:
                a = b = c - 1
            elif a == b:
                discrete = True
                a -= 1
                b += 1
            else:
                a -= 1
                b += 1
                if a < 0:
                    a = 1 if discrete else 0
                if b > c:
                    b = c - 1 if discrete else c
    return True

l, r = 0, len(s)
while r - l > 1:
    c = (l + r) // 2
    if test(c):
        r = c
    else:
        l = c
print(r)

Submission status: Time Limit Exceeded

Solution code:
from numba import njit
s = input()

@njit
def test(c):
    # current point can be seen as xth smallest val, where x can be any value in [a, b] (subset of [0, c])
    # a <= b
    a, b = 0, c
    ok = True
    discrete = False # when True x = a, a+2, ..., b-2, b
    for si in s:
        if si == '1':
            if a == b == c:
                return False
            a += 1
            b += 1
            if b > c:
                b = c - 1 if discrete else c
        elif si == '0':
            if a == b == 0:
                return False
            a -= 1
            b -= 1
            if a < 0:
                a = 1 if discrete else 0
        else:
            if a == b == 0:
                a = b = 1
            elif a == b == c:
                a = b = c - 1
            elif a == b:
                discrete = True
                a -= 1
                b += 1
            else:
                a -= 1
                b += 1
                if a < 0:
                    a = 1 if discrete else 0
                if b > c:
                    b = c - 1 if discrete else c
    return True


l, r = 0, len(s)
while r - l > 1:
    c = (l + r) // 2
    if test(c):
        r = c
    else:
        l = c
print(r)

Submission status: Time Limit Exceeded

Solution code:
s = input()

l, r = 0, len(s)
while r - l > 1:
    c = (l + r) // 2
    
    # current point can be seen as xth smallest val, where x can be any value in [a, b] (subset of [0, c])
    # a <= b
    a, b = 0, c
    ok = True
    discrete = False # when True x = a, a+2, ..., b-2, b
    for si in s:
        if si == '1':
            if a == b == c:
                ok = False
                break
            a += 1
            b += 1
            if b > c:
                b = c - 1 if discrete else c
        elif si == '0':
            if a == b == 0:
                ok = False
                break
            a -= 1
            b -= 1
            if a < 0:
                a = 1 if discrete else 0
        else:
            if a == b == 0:
                a = b = 1
            elif a == b == c:
                a = b = c - 1
            elif a == b:
                discrete = True
                a -= 1
                b += 1
            else:
                a -= 1
                b += 1
                if a < 0:
                    a = 1 if discrete else 0
                if b > c:
                    b = c - 1 if discrete else c
    if ok:
        r = c
    else:
        l = c
print(r)

Submission status: Time Limit Exceeded

Solution code:
s = input()

l, r = 0, len(s)
while r - l > 1:
    c = (l + r) // 2
    
    # current point can be seen as xth smallest val, where x can be any value in [a, b] (subset of [0, c])
    # a <= b
    a, b = 0, c
    ok = True
    discrete = False # when True x = a, a+2, ..., b-2, b
    for si in s:
        if si == '1':
            if a == b == c:
                ok = False
                break
            a += 1
            b += 1
            if b > c:
                b = c - 1 if discrete else c
        elif si == '0':
            if a == b == 0:
                ok = False
                break
            a -= 1
            b -= 1
            if a < 0:
                a = 1 if discrete else 0
        else:
            if a == b == 0:
                a = b = 1
            elif a == b == c:
                a = b = c - 1
            elif a == b:
                discrete = True
                a -= 1
                b += 1
            else:
                a -= 1
                b += 1
                if a < 0:
                    a = 1 if discrete else 0
                if b > c:
                    b = c - 1 if discrete else c
    if ok:
        r = c
    else:
        l = c
print(r)

Submission status: Time Limit Exceeded

Solution code:

def bisect(ng, ok, judge):
    while abs(ng-ok) > 1:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

def solve(S):
    d = {'0':(-1,-1),'1':(1,1),'?':(-1,1)}
    S = [d[c] for c in S]

    def judge(target_lo, target_hi):
        lo = 0
        hi = 0

        pl = target_lo%2 == 0
        ph = target_hi%2 == 0

        for a,b in S:
            lo = max(lo+a, target_lo+pl)
            hi = min(hi+b, target_hi-ph)
            if hi < lo:
                return False
            pl = not pl
            ph = not ph
        return True

    best = 10**6*2
    lo = -10**6
    hi = 10**6
    while True:
        hi = bisect(-1,10**6, lambda x: judge(lo, x))
        lo = bisect(1, -10**6, lambda x: judge(x, hi))
        if hi-lo >= best:
            break
        else:
            best = hi-lo
    hi += 1
    lo = bisect(1, -10**6, lambda x: judge(x, hi))
    return min(best, hi-lo)

from itertools import product, accumulate
from random import shuffle

def naive(S):
    d = {'0':(-1,), '1':(1,), '?': (-1,1)}
    return min(max(0,max(accumulate(X)))-min(0,min(accumulate(X))) for X in product(*(d[c] for c in S)))

if __name__ == '__main__':
    S = input()
    print(solve(S))

    # for _ in range(50):
    #     S = ['0']*15+['1']*15+['?']*14
    #     shuffle(S)
    #     S = ''.join(S)
    #     print(S, naive(S), solve(S))

Submission status: Time Limit Exceeded

Solution code:

def bisect(ng, ok, judge):
    while abs(ng-ok) > 1:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

def solve(S):
    d = {'0':-1,'1':1,'?':0}
    S = [d[c] for c in S]

    def judge(target_lo, target_hi):
        lo = 0
        hi = 0
        for s in S:
            if s == 0:
                lo -= 1
                hi += 1
            elif s == 1:
                lo += 1
                hi += 1
            else:
                lo -= 1
                hi -= 1
            hi = min(hi, target_hi-(target_hi+hi)%2)
            lo = max(lo, target_lo+(target_lo+lo)%2)
            if hi < lo:
                return False
        return True

    best = 10**6*2
    lo = -10**6
    hi = 10**6
    while True:
        hi = bisect(-1,10**6, lambda x: judge(lo, x))
        lo = bisect(1, -10**6, lambda x: judge(x, hi))
        if hi-lo >= best:
            break
        else:
            best = hi-lo
    hi += 1
    lo = bisect(1, -10**6, lambda x: judge(x, hi))

    best = min(best, hi-lo)
    return best

from itertools import product, accumulate
from random import shuffle

def naive(S):
    d = {'0':(-1,), '1':(1,), '?': (-1,1)}
    return min(max(0,max(accumulate(X)))-min(0,min(accumulate(X))) for X in product(*(d[c] for c in S)))

if __name__ == '__main__':
    S = input()
    print(solve(S))

    # for _ in range(50):
    #     S = ['0']*15+['1']*15+['?']*14
    #     shuffle(S)
    #     S = ''.join(S)
    #     print(S, naive(S), solve(S))

Submission status: Time Limit Exceeded

Solution code:
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)
# dp[now]: max,min
dp = defaultdict(set)
dp[0] = {(0, 0)}
for i, c in enumerate(S):
    ndp = defaultdict(set)
    if c != '0':
        for k, li in dp.items():
            for ma, mi in li:
                ndp[k + 1].add((max(ma, k + 1), mi))
    if c != '1':
        for k, li in dp.items():
            for ma, mi in li:
                ndp[k - 1].add((ma, min(mi, k - 1)))
    dp = ndp
ans = INF
for li in dp.values():
    for a, b in li:
        ans = min(ans, abs(a - b))
print(ans)

# # 後ろに見てったとき、max を i にするときの最大の min
# max_mins = [-np.inf] * (N + 10)
# max_mins[0] = 0
# max_mins = np.array(max_mins, dtype=float)
# for c in reversed(S):
#     if c == '0':
#         # -1にする
#         zero = max_mins[0]
#         max_mins[:-1] = max_mins[1:] - 1
#         max_mins[0] = max(max_mins[0], zero - 1)
#     elif c == '1':
#         # 1にする
#         max_mins[1:] = np.minimum(0, max_mins[:-1] + 1)
#         max_mins[0] = -np.inf
#     else:
#         # 1にする
#         tmp = np.array(max_mins)
#         zero = tmp[0]
#         max_mins[:-1] = tmp[1:] - 1
#         max_mins[0] = max(max_mins[0], zero - 1)
#         max_mins[1:] = np.maximum(max_mins[1:], np.minimum(0, tmp[:-1] + 1))
#     print(max_mins)


# # 後ろに見てったとき、max を i にするときの最大の min
# imos = deque([0] * (N + 10))
# max_mins = deque([-INF] * (N + 10))
# max_mins[0] = 0
# for c in reversed(S):
#     max_mins[0] += imos[0]
#     imos[1] += imos[0]
#     imos[0] = 0
#     if c == '0':
#         # -1にする
#         zero = max_mins[0]
#         max_mins.popleft()
#         imos.popleft()
#         imos[1] -= 1
#         max_mins[0] -= 1
#         max_mins[0] = max(max_mins[0], zero - 1)
#     elif c == '1':
#         # 1にする
#         imos[1] += 1
#         max_mins[1:] = np.minimum(0, max_mins[:-1] + 1)
#         max_mins[0] = -np.inf
#         max_mins.appendleft(-INF)
#         imos.appendleft(0)
#     else:
#         # 1にする
#         tmp = np.array(max_mins)
#         zero = tmp[0]
#         max_mins[:-1] = tmp[1:] - 1
#         max_mins[0] = max(max_mins[0], zero - 1)
#         max_mins[1:] = np.maximum(max_mins[1:], np.minimum(0, tmp[:-1] + 1))
#     print(max_mins)

Submission status: Time Limit Exceeded

Solution code:
def unbalance(S):
    max_sum0 = 0
    now_sum0 = 0
    max_sum1 = 0
    now_sum1 = 0
    for i in range(len(S)):
        if S[i] == "0":
            now_sum0 += 1
            now_sum1 = max(now_sum1 - 1, 0)
        else:
            now_sum0 = max(now_sum0 - 1, 0)
            now_sum1 += 1
        max_sum0 = max(max_sum0, now_sum0)
        max_sum1 = max(max_sum1, now_sum1)
    return max(max_sum0, max_sum1)

def solve(S):
    st = "" # debug
    if S[0] == "?":
        for i in range(len(S)):
            if S[i] == "0":
                if i % 2 == 0:
                    S[0] = "0"
                else:
                    S[0] = "1"
                break
            elif S[i] == "1":
                if i % 2 == 0:
                    S[0] = "1"
                else:
                    S[0] = "0"
                break
    if S[0] == "?":
        return 1

    now_sum0 = 0
    now_sum1 = 0
    un = 1
    val = -1
    for i in range(len(S)):
        if S[i] == "0":
            now_sum0 += 1
            now_sum1 = max(now_sum1 - 1, 0)
            val = -1
            st += "0" # debug
        elif S[i] == "1":
            now_sum0 = max(now_sum0 - 1, 0)
            now_sum1 += 1
            val = -1
            st += "1" # debug
        else :
            if now_sum0 > now_sum1:
                if now_sum0 > now_sum1 + 1:
                    now_sum1 += 1
                    now_sum0 = max(now_sum0 - 1, 0)
                    st += "1" # debug
                elif i + 1 < len(S):
                    if S[i+1] == "0":
                        now_sum0 = max(now_sum0 - 1, 0)
                        now_sum1 += 1
                        st += "1" # debug
                    elif S[i+1] == "1":
                        now_sum0 += 1
                        now_sum1 = max(now_sum1 - 1, 0)
                        st += "0" # debug
                    else:
                        now_sum1 += 1
                        now_sum0 = max(now_sum0 - 1, 0)
                        st += "1" # debug
            elif now_sum1 > now_sum0:
                if now_sum1 > now_sum0 + 1:
                    now_sum0 += 1
                    now_sum1 = max(now_sum1 - 1, 0)
                    st += "0" # debug
                elif i + 1 < len(S):
                    if S[i+1] == "0":
                        now_sum0 = max(now_sum0 - 1, 0)
                        now_sum1 += 1
                        st += "1" # debug
                    elif S[i+1] == "1":
                        now_sum0 += 1
                        now_sum1 = max(now_sum1 - 1, 0)
                        st += "0" # debug
                    else:
                        now_sum0 += 1
                        now_sum1 = max(now_sum1 - 1, 0)
                        st += "0" # debug
            else:
                if i + 1 < len(S):
                    if S[i+1] == "0":
                        now_sum0 = max(now_sum0 - 1, 0)
                        now_sum1 += 1
                        st += "1" # debug
                    elif S[i+1] == "1":
                        now_sum0 += 1
                        now_sum1 = max(now_sum1 - 1, 0)
                        st += "0" # debug
                    else:                   
                        if val == -1:
                            for j in range(i, len(S)):
                                if S[j] == "0":
                                    if (j - i) % 2 == 0:
                                        val = 0
                                    else:
                                        val = 1
                                    break
                                elif S[j] == "1":
                                    if (j - i) % 2 == 0:
                                        val = 1
                                    else:
                                        val = 0
                                    break
                        if val == 1:
                            now_sum0 = max(now_sum0 - 1, 0)
                            now_sum1 += 1
                            st += "1" # debug
                        elif val == 0:
                            now_sum0 += 1
                            now_sum1 = max(now_sum1 - 1, 0)
                            st += "0" # debug
                        else:
                            return unbalance(st)
                else:
                    return unbalance(st)
    return unbalance(st)

S = list(input())
print(min(solve(S), solve(S[::-1])))

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/agc045/tasks/agc045_b

交互が最高
アンバランス度の定義を変えたい
1の数 = 区間和
0の数 = 区間長さ-1の数
アンバランス度 = abs(区間長さ - 区間和 * 2)
→ abs( r-l+1 - (dp[r]-dp[l])*2 )
  =abs( r-dp[r]*2 - (l-dp[l]*2) + 1 )

アンバランス度は2分探索すればよさそう
あとは、アンバランス度x以下を達成できるか？
の判定問題

連続してxこ並ぶ場所があると不可能
アンバランス度は、 (l-dp[l]*2) の最大・最小値さえ持っておけば計算できる
x以下を達成する方法は？

始めて?が来た時を考える
今までの (l-dp[l]*2) の最大・最小値 は持っている
なるべく最大・最小値は更新しない方がいい
1にする→1減らす
0にする→1増やす

1増やす・1減らすを選んで差を x-1以下にしたい問題
まず全部上にしておく
それ以降の最大値と最小値に影響する
下にすると、最大値を-2,最小値も-2できる

それ以前の最大値-それ以降の最小値 は2ふえる
それ以降の最大値-それ以前の最小値 は2へる
y=xを足してみる

====答えを見た=====

maspy氏の方針がわかりやすい
https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2020-06-07agc045
行ける点は連番になる(偶奇は違うので注意)
x以下が可能か → 0以上x以下の点からスタートして,維持できるか

なぜ偶奇の場合分けが必要？
→平行移動が不可能だからありえない答えを生み出す可能性があるため

ある数字以外不可能な時=幅が2になり、3つの数字の可能性が生まれるが
平行移動はできないため、存在しえない数字が生まれてしまう

偶奇をちゃんとすれば問題ない


"""

from sys import stdin

S = stdin.readline()
S = S[:-1]
N = len(S)

r = 2*10**6
l = 0
while r-l != 1:
    m = (r+l)//2
    flag = False

    #even
    nmax = m//2*2
    nmin = 0
    for i in range(N):
        if S[i] == "0":
            nmax = min(nmax+1,m)
            nmin = min(nmin+1,m)
        elif S[i] == "1":
            nmax = max(nmax-1,0)
            nmin = max(nmin-1,0)
        else:
            nmax = min(nmax+1,m)
            nmin = max(nmin-1,0)
            
        if i % 2 == 0:
            if nmax % 2 == 0:
                nmax -= 1
            if nmin % 2 == 0:
                nmin += 1
        else:
            if nmax % 2 == 1:
                nmax -= 1
            if nmin % 2 == 1:
                nmin += 1

        if nmax < nmin:
            break

    if nmax >= nmin:
        flag = True
    else:
        #odd
        nmax = (m-1)//2*2+1
        nmin = 1
        for i in range(N):
            if S[i] == "0":
                nmax = min(nmax+1,m)
                nmin = min(nmin+1,m)
            elif S[i] == "1":
                nmax = max(nmax-1,0)
                nmin = max(nmin-1,0)
            else:
                nmax = min(nmax+1,m)
                nmin = max(nmin-1,0)
                
            if i % 2 == 1:
                if nmax % 2 == 0:
                    nmax -= 1
                if nmin % 2 == 0:
                    nmin += 1
            else:
                if nmax % 2 == 1:
                    nmax -= 1
                if nmin % 2 == 1:
                    nmin += 1

            if nmax < nmin:
                break
        if nmax >= nmin:
            flag = True

    if flag:
        r = m
    else:
        l = m

print (r)

Submission status: Accepted

Solution code:
from itertools import accumulate

S = input()
N = len(S)

A = [0] + list(accumulate(1 if s == "1" else -1 for s in S))

ma = max(A)
cur = A[-1]
C = [ma - cur]
for a in reversed(A):
    cur = max(a, cur)
    C.append(ma - cur)

d, e = 0, 0
D, E = A[:], A[:]
for i, (s, c) in enumerate(zip(S, reversed(C[:-1])), 1):
    if s == '?' and c >= d + 2:
        d += 2
    if s == '?' and c >= e + 1:
        e += 2
    D[i] += d
    E[i] += e

print(min(max(D) - min(D), max(E) - min(E)))

Submission status: Accepted

Solution code:
from itertools import accumulate
import copy

S=input()
ANS=[0]
for s in S:
    if s=="0":
        ANS.append(-1)
    else:
        ANS.append(1)
SUM=list(accumulate(ANS))
MIN=[SUM[-1]]
for s in SUM[::-1][1:]:
    MIN.append(min(MIN[-1],s))
MIN.reverse()
MX=min(MIN)

ANS2=copy.deepcopy(ANS)
sa=0
for i in range(len(S)):
    if S[i]=="?":
        if MIN[i+1]-MX-sa>=2:
            ANS2[i+1]=-1
            sa+=2

ANS3=copy.deepcopy(ANS)
sa=0
MX-=1
for i in range(len(S)):
    if S[i]=="?":
        if MIN[i+1]-MX-sa>=2:
            ANS3[i+1]=-1
            sa+=2

S2=list(accumulate(ANS2))
S3=list(accumulate(ANS3))

print(min(max(S2)-min(S2),max(S3)-min(S3)))

Submission status: Accepted

Solution code:
def main():
    S = input()
    size = [[[[0, 0]], []], [[], []]]
    length = 0

    for s in S:
        size2 = [[[], []], [[], []], [[], []]]
        if s != "0":
            for i in range(2):
                for j in range(2):
                    if size[i][j]:
                        for x, y in size[i][j]:
                            if y == length+i:
                                size2[i+1][j ^ 1].append([y+1, y+1])
                                if x != y:
                                    size2[i][j ^ 1].append([x+1, y-1])
                            else:
                                size2[i][j ^ 1].append([x+1, y+1])
        if s != "1":
            for i in range(2):
                for j in range(2):
                    if size[i][j]:
                        for x, y in size[i][j]:
                            if x == 0:
                                size2[i+1][j].append([0, 0])
                                if x != y:
                                    size2[i][j ^ 1].append([x+1, y-1])
                            else:
                                size2[i][j ^ 1].append([x-1, y-1])
        if len(size2[0][0]+size2[0][1]) == 0:
            size2 = size2[1:]
            length += 1
        else:
            size2.pop()
        for i in range(2):
            for j in range(2):
                size2[i][j] = sorted(size2[i][j])
        size = [[[], []], [[], []]]
        for i in range(2):
            for j in range(2):
                if len(size2[i][j]) == 0:
                    continue
                size[i][j] = [size2[i][j][0]]
                for x, y in size2[i][j][1:]:
                    size[i][j][-1][1] = max(y, size[i][j][-1][1])

    print(length)


main()