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

Solution (Python):

"""

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

    
    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:
        
        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)

Solution (Python):
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)))

Solution (Python):
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)))

Solution (Python):
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()

Solution (Python):
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
                elif len(size2[i][j]) == 1:
                    size[i][j] = size2[i][j]
                    continue
                size[i][j] = [size2[i][j][0]]
                for x, y in size2[i][j][1:]:
                    p, q = size[i][j][-1]
                    if y <= q:
                        continue
                    if x <= q+2:
                        size[i][j][-1][1] = y
                    else:
                        size[i][j].append([x, y])
    print(length)


main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
S = input()

c = 0
cum = [c]
for s in S:
    if s == "1":
        c += 1
    else:
        c -= 1
    cum.append(c)
max_cum = [None] * (len(S) + 1)
max_cum[-1] = cum[-1]
for i in reversed(range(len(S))):
    max_cum[i] = max(cum[i], max_cum[i + 1])
z = max_cum[0]


def f(m):
    c = 0
    fz = c
    add = 0
    for i, s in enumerate(S):
        if s == "1":
            c += 1
        elif s == "0":
            c -= 1
            fz = min(fz, c)
        elif add + max_cum[i + 1] + 2 <= m:
            c += 1
            add += 2
        else:
            c -= 1
            fz = min(fz, c)
    return fz


fz = f(z)
fz1 = f(z + 1)

ans = min(z - fz, z + 1 - fz1)
print(ans)

Solution (Python):
S = input()

c = 0
cum = [c]
for s in S:
    if s == "1":
        c += 1
    else:
        c -= 1
    cum.append(c)
max_cum = [None] * (len(S) + 1)
max_cum[-1] = cum[-1]
for i in reversed(range(len(S))):
    max_cum[i] = max(cum[i], max_cum[i + 1])
z = max_cum[0]


def f(m):
    c = 0
    fz = c
    add = 0
    for i, s in enumerate(S):
        if s == "1":
            c += 1
        elif s == "0":
            c -= 1
            fz = min(fz, c)
        elif add + max_cum[i + 1] + 2 <= m:
            c += 1
            add += 2
        else:
            c -= 1
            fz = min(fz, c)
    return fz


fz = f(z)
fz1 = f(z + 1)

ans = min(z - fz, z + 1 - fz1)
print(ans)

Solution (Python):
from numba import njit
import numpy as np
s = np.array(list(map(lambda x: -1 if x == '?' else int(x), input())))
@njit
def test(c):
    
    
    a, b = 0, c
    ok = True
    discrete = False 
    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, s.size
while r - l > 1:
    c = (l + r) // 2
    if test(c):
        r = c
    else:
        l = c
print(r)

Solution (Python):
S = input()
N = len(S)

A = [0]*(N+1)
for i,s in enumerate(S,1):
    if s=="1":
        A[i] = A[i-1]+1
    else:
        A[i] = A[i-1]-1

m = max(A)
B = [A[-1]]*(N+1)
C = [m-A[-1]]*(N+1)
for i in range(N):
    i = N-i-1
    B[i] = max(A[i],B[i+1])
    C[i] = m-B[i]

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

Solution (Python):
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8[::1],i8)', cache=True)
def test(S, A):
    def f(L, R):
        if L > R:
            return False
        for x in S:
            if x == 1:
                L, R = L + 1, R + 1
                if R > A:
                    R -= 2
            elif x == -1:
                L, R = L - 1, R - 1
                if L < 0:
                    L += 2
            else:
                L -= 1
                R += 1
                if L < 0:
                    L += 2
                if R > A:
                    R -= 2
            if L > R:
                return False
        return True

    for parity in (0, 1):
        L, R = 0, A
        if parity == 0:
            R -= A & 1
        else:
            L = 1
            R -= 1 - (A & 1)
        if f(L, R):
            return True
    return False

S = np.array(list(read().rstrip().decode()), 'U1')
Si = np.zeros(len(S), np.int64)
Si[S == '0'] = -1
Si[S == '1'] = 1
S = Si

low = 0  
high = len(S) + 10  
while low + 1 < high:
    x = (low + high) // 2
    if test(S, x):
        high = x
    else:
        low = x

print(high)

Solution (Python):
S = list(input())
N = len(S)


Z = 0
SUM = 0
for s in S:
  if s == "1":
    SUM += 1
    Z = max(Z,SUM)
  else:
    SUM -= 1

ruiseki_max = [0]
MAX = SUM
for s in S[1:][::-1]:
  if s == "1":
    SUM -= 1
  else:
    SUM += 1
    MAX = max(MAX,SUM)
  ruiseki_max.append(MAX-SUM)

def f(Z):
  SUM = 0
  MIN = 0
  for i in range(N):
    s = S[i]
    if s == "1":
      SUM += 1
    elif s == "0":
      SUM -= 1
      MIN = min(MIN,SUM)
    else:
      if SUM + 1 + ruiseki_max[N-1-i] <= Z:
        SUM += 1
      else:
        SUM -= 1
        MIN = min(MIN,SUM)
  return MIN

print(min(Z-f(Z),(Z+1-f(Z+1))))

Solution (Python):

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':0,'1':1,'?':2}
    S = tuple(d[c] for c in S)
    lookup = ((-1,-1),(1,1), (-1,1))

    def judge(target_lo, target_hi):
        lo,hi = 0,0
        pl = target_lo%2 == 0
        ph = target_hi%2 == 0
        for s in S:
            a,b = lookup[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
    n0,n1,n2 = S.count(0), S.count(1), S.count(2)
    lo = -n0-n2
    hi = n1+n2
    while True:
        hi = bisect(-1, hi, lambda x: judge(lo, x))
        lo = bisect(1, lo, lambda x: judge(x, hi))
        if hi-lo >= best:
            break
        else:
            best = hi-lo
    hi += 1
    lo = bisect(1, lo, lambda x: judge(x, hi))
    return min(best, hi-lo)








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

Solution (Python):
S = input()

max0 = 0
max1 = 0
amax0 = []
amax1 = []
mi0 = 0
mi1 = 0
h0 = 0
h1 = 0
for i, c in enumerate(S):
    if c=="1":
        h1 += 1
        if h1-mi1 > max1:
            max1 = h1-mi1
            amax1 = [i]
        elif h1-mi1 == max1:
            amax1.append(i)
        h0 -= 1
        if h0 < mi0:
            mi0 = h0
    elif c=="0":
        h1 -= 1
        if h1 < mi1:
            mi1 = h1
        h0 += 1
        if h0-mi0 > max0:
            max0 = h0-mi0
            amax0 = [i]
        elif h0-mi0 == max0:
            amax0.append(i)
    else:
        h1 -= 1
        if h1 < mi1:
            mi1 = h1
        h0 -= 1
        if h0 < mi0:
            mi0 = h0
if max0 < max1:
    if len(set([i%2 for i in amax1]))==1:
        print(max1)
    else:
        print(max1+1)
elif max0 > max1:
    if len(set([i%2 for i in amax0]))==1:
        print(max0)
    else:
        print(max0+1)
else:
    if len(set([i%2 for i in amax1]+[(max0+i)%2 for i in amax0]))==1:
        print(max0)
    else:
        print(max0+1)

Solution (Python):
S = input()

max0 = 0
max1 = 0
amax0 = []
amax1 = []
mi0 = 0
mi1 = 0
h0 = 0
h1 = 0
for i, c in enumerate(S):
    if c=="1":
        h1 += 1
        if h1-mi1 > max1:
            max1 = h1-mi1
            amax1 = [i]
        elif h1-mi1 == max1:
            amax1.append(i)
        h0 -= 1
        if h0 < mi0:
            mi0 = h0
    elif c=="0":
        h1 -= 1
        if h1 < mi1:
            mi1 = h1
        h0 += 1
        if h0-mi0 > max0:
            max0 = h0-mi0
            amax0 = [i]
        elif h0-mi0 == max0:
            amax0.append(i)
    else:
        h1 -= 1
        if h1 < mi1:
            mi1 = h1
        h0 -= 1
        if h0 < mi0:
            mi0 = h0






if max0 < max1:
    if len(set([i%2 for i in amax1]))==1:
        print(max1)
    else:
        print(max1+1)
elif max0 > max1:
    if len(set([i%2 for i in amax0]))==1:
        print(max0)
    else:
        print(max0+1)
else:
    if len(set([i%2 for i in amax1]+[(max0+i)%2 for i in amax0]))==1:
        print(max0)
    else:
        print(max0+1)