Problem:
 Score : 600 points    Problem Statement Snuke stands on a number line. He has L ears, and he will walk along the line continuously under the following conditions:   He never visits a point with coordinate less than 0 , or a point with coordinate greater than L .  He starts walking at a point with integer coordinate, and also finishes walking at a point with integer coordinate.  He only changes direction at a point with integer coordinate.   Each time when Snuke passes a point with coordinate i-0.5 , where i is an integer, he put a stone in his i -th ear.  After Snuke finishes walking, Ringo will repeat the following operations in some order so that, for each i , Snuke's i -th ear contains A_i stones:   Put a stone in one of Snuke's ears.  Remove a stone from one of Snuke's ears.   Find the minimum number of operations required when Ringo can freely decide how Snuke walks.      Constraints  1 \leq L \leq 2\times 10^5  0 \leq A_i \leq 10^9(1\leq i\leq L)  All values in input are integers.         Input Input is given from Standard Input in the following format:  L  A_1  :  A_L       Output Print the minimum number of operations required when Ringo can freely decide how Snuke walks.        Sample Input 1 4
1
0
2
3      Sample Output 1 1  Assume that Snuke walks as follows:   He starts walking at coordinate 3 and finishes walking at coordinate 4 , visiting coordinates 3,4,3,2,3,4 in this order.   Then, Snuke's four ears will contain 0,0,2,3 stones, respectively.
Ringo can satisfy the requirement by putting one stone in the first ear.       Sample Input 2 8
2
0
0
2
1
3
4
1      Sample Output 2 3       Sample Input 3 7
314159265
358979323
846264338
327950288
419716939
937510582
0      Sample Output 3 1

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


l = int(input())
a = [None]*l
for i in range(l):
    a[i] = int(input())
dp = [[float("inf")]*(l+1) for _ in range(5)]
for i in range(5):
    dp[i][0] = 0
def c1(v):
    if v==0:
        return 2
    else:
        return v%2
def c2(v):
    if v%2==0:
        return 1
    else:
        return 0
for i in range(1,l+1):
    v = a[i-1]
    m = dp[0][i-1]
    dp[0][i] = m + v
    m = min(m, dp[1][i-1])
    dp[1][i] = m + c1(v)
    m = min(m, dp[2][i-1])
    dp[2][i] = m + c2(v)
    m = min(m, dp[3][i-1])
    dp[3][i] = m + c1(v)
    m = min(m, dp[4][i-1])
    dp[4][i] = m + v
ans = min(dp[i][l] for i in range(5))
print(ans)

Solution (Python):
l = int(input())
a = [int(input()) for _ in range(l)]
a.insert(0, 0)
dp = [[1000000] * (l + 1) for _ in range(4)]
for i in range(4):
    dp[i][0] = 0
for i in range(1, l + 1):
    dp[0][i] = dp[0][i - 1] + a[i]
for i in range(1, 4):
    for j in range(1, l + 1):
        if i == 2:
            x = abs(a[j] % 2 - 1)
        else:
            x = abs(2 - min(a[j] % 2 + 2, a[j]))
        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1] + x)
ans = dp[3][l]
s = 0
for i in range(l - 1, -1, -1):
    s += a[i + 1]
    ans = min(ans, dp[3][i] + s)
print(ans)

Solution (Python):
L=int(input())
A=[int(input()) for i in range(L)]
INF=10**16
DP=[[INF]*5 for i in range(L+1)]
DP[0]=[0]*5
for i in range(L):
  for j in range(5):
    DP[i+1][4]=min(DP[i+1][4],DP[i][j]+A[i])
  DP[i+1][0]=DP[i][0]+A[i]
  for k in [1,3]:
    for j in range(k+1):
      if A[i]:
        DP[i+1][k]=min(DP[i+1][k],DP[i][j]+(A[i]&1))
      else:
        DP[i+1][k]=min(DP[i+1][k],DP[i][j]+2)
  for j in range(3):
    DP[i+1][2]=min(DP[i+1][2],DP[i][j]+1-(A[i]&1))
print(min(DP[L]))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
inf = 10**18

N = int(input())
A = tuple(int(input()) for _ in range(N))

"""
0: zero_L
1: even_L
2: odd
3: even_R
4: zero_R
"""
dp = [inf] * 5
for i, a in enumerate(A):
    if i == 0:
        if a == 0:
            dp[0] = a
            dp[1] = 2
            dp[2] = 1
            dp[3] = 2
            dp[4] = a
        elif a % 2 == 0:
            dp[0] = a
            dp[1] = 0
            dp[2] = 1
            dp[3] = 0
            dp[4] = a
        else:
            dp[0] = a
            dp[1] = 1
            dp[2] = 0
            dp[3] = 1
            dp[4] = a
        continue

    newDP = [inf]*5
    if a == 0:
        newDP[0] = dp[0] + a
        newDP[1] = min(dp[0], dp[1]) + 2
        newDP[2] = min(dp[0], dp[1], dp[2]) + 1
        newDP[3] = min(dp[0], dp[1], dp[2], dp[3]) + 2
        newDP[4] = min(dp[0], dp[1], dp[2], dp[3], dp[4]) + a
    elif a % 2 == 1:
        newDP[0] = dp[0] + a
        newDP[1] = min(dp[0], dp[1]) + 1
        newDP[2] = min(dp[0], dp[1], dp[2])
        newDP[3] = min(dp[0], dp[1], dp[2], dp[3]) + 1
        newDP[4] = min(dp[0], dp[1], dp[2], dp[3], dp[4]) + a
    else:
        newDP[0] = dp[0] + a
        newDP[1] = min(dp[0], dp[1])
        newDP[2] = min(dp[0], dp[1], dp[2]) + 1
        newDP[3] = min(dp[0], dp[1], dp[2], dp[3])
        newDP[4] = min(dp[0], dp[1], dp[2], dp[3], dp[4]) + a
    dp = newDP

print(min(dp))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    inf=10**16
    aa=[II() for _ in range(n)]

    dpl=[inf]*(n+1)
    dpl[0]=0
    s=0
    for i in range(n):
        a=aa[i]
        s+=a
        dpl[i+1]=s
        if a==0:dpl[i+1]=min(dpl[i+1],dpl[i]+2)
        else:dpl[i+1]=min(dpl[i+1],dpl[i]+a%2)
    

    dpr=[inf]*(n+1)
    dpr[n]=0
    s=0
    for i in range(n-1,-1,-1):
        a=aa[i]
        s+=a
        dpr[i]=s
        if a==0:dpr[i]=min(dpr[i],dpr[i+1]+2)
        else:dpr[i]=min(dpr[i],dpr[i+1]+a%2)
    

    even=[0]
    for a in aa:
        if a%2:even.append(even[-1])
        else:even.append(even[-1]+1)
    

    mn=inf
    ans=inf
    for i in range(n+1):
        mn=min(mn,dpl[i]-even[i])
        cur=mn+dpr[i]+even[i]
        ans=min(ans,cur)
    
    print(ans)

main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

l = int(readline())
a = list(map(int,read().split()))

dp = [[0] * (l+1) for _ in range(5)]

for i in range(l):
    dp[0][i+1] = dp[0][i] + a[i]

for i in range(l):
    dp[1][i+1] = min(dp[0][i+1],
                    min(dp[0][i], dp[1][i]) + (a[i]%2 if a[i]!=0 else 2))

for i in range(l):
    dp[2][i+1] = min(dp[1][i+1],
                    min(dp[0][i], dp[1][i], dp[2][i]) + (a[i]-1)%2)

for i in range(l):
    dp[3][i+1] = min(dp[2][i+1],
                    min(dp[0][i], dp[1][i], dp[2][i], dp[3][i]) + (a[i]%2 if a[i]!=0 else 2))

for i in range(l):
    dp[4][i+1] = min(dp[3][i+1],
                    min(dp[0][i], dp[1][i], dp[2][i], dp[3][i], dp[4][i]) + a[i])

print(dp[-1][-1])

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]

dp = [[0]*5 for _ in range(N+1)]

for i, a in enumerate(A):
    b = a%2 if a > 0 else 2
    dp[i+1][0] = dp[i][0] + a
    dp[i+1][1] = min(dp[i][1], dp[i][0]) + b
    dp[i+1][2] = min([dp[i][2], dp[i][1], dp[i][0]]) + (a+1)%2
    dp[i+1][3] = min([dp[i][3], dp[i][2], dp[i][1], dp[i][0]]) + b
    dp[i+1][4] = min(dp[i]) + a

ans = min([dp[N][4], dp[N][3], dp[N][2]])
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

L = int(input())
A = [int(input()) for _ in range(L)]
INF = 10**18
dp = [[INF] * 5 for _ in range(L+1)]
dp[0][0] = 0

for i in range(L):
    for j in range(5):
        for k in range(j, 5):
            if k in (0, 4): 
                dp[i+1][k] = min(dp[i+1][k], dp[i][j] + A[i])
            if k in (1, 3): 
                if A[i] == 0:
                    dp[i+1][k] = min(dp[i+1][k], dp[i][j] + 2)
                else:
                    dp[i+1][k] = min(dp[i+1][k], dp[i][j] + (A[i] % 2))
            if k == 2: 
                if A[i] == 0:
                    dp[i+1][k] = min(dp[i+1][k], dp[i][j] + 1)
                else:
                    dp[i+1][k] = min(dp[i+1][k], dp[i][j] + 1 - (A[i] % 2))
print(min(dp[L]))

Solution (Python):
N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))

dat=[A[i] for i in range(N)]
for i in range(1,N):
    dat[i]+=dat[i-1]

evenf=[0]*N
evenf[0]=A[0]%2
for i in range(1,N):
    t=A[i]%2
    if A[i]==0:
        t=2
    evenf[i]=min(evenf[i-1]+t,dat[i])

evenb=[0]*N
evenb[N-1]=A[-1]%2
for i in range(N-2,-1,-1):
    t=A[i]%2
    if A[i]==0:
        t=2
    if i!=0:
        evenb[i]=min(evenb[i+1]+t,dat[-1]-dat[i-1])
    else:
        evenb[i]=min(evenb[i+1]+t,dat[-1])

oddf=[0 for i in range(N)]
for i in range(1,N):
    t=(1+A[i])%2
    oddf[i]=min(oddf[i-1]+t,evenf[i])

ans=oddf[-1]
for i in range(N-1):
    ans=min(ans,evenb[i+1]+oddf[i])

print(ans)

Solution (Python):
L = int(input())
A = [int(input()) for _ in range(L)]
dp = [[1 << 60] * 5 for _ in range(L + 1)]
dp[0] = [0] * 5
for i in range(1, L + 1):
    a = A[i - 1]
    dp[i][0] = dp[i - 1][0] + a
    tm = min(dp[i - 1][0], dp[i - 1][1])
    dp[i][1] = tm + (2 if a == 0 else a % 2)
    tm = min(tm, dp[i - 1][2])
    dp[i][2] = tm + (1 - a % 2)
    tm = min(tm, dp[i - 1][3])
    dp[i][3] = tm + (2 if a == 0 else a % 2)
    tm = min(tm, dp[i - 1][4])
    dp[i][4] = tm + a
print(min(dp[L]))

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

L = ni()

A = [ni() for _ in range(L)]
assert len(A) == L

INF = 1 << 60
S = 5  


def solve():
    dp = [[INF] * S for _ in range(L + 1)]
    for s in range(S):
        dp[0][s] = 0
    for i in range(1, L + 1):
        a = A[i - 1]
        dp[i][0] = dp[i - 1][0] + a
        tm = min(dp[i - 1][0], dp[i - 1][1])
        dp[i][1] = tm + (2 if a == 0 else a % 2)
        tm = min(tm, dp[i - 1][2])
        dp[i][2] = tm + (1 - a % 2)
        tm = min(tm, dp[i - 1][3])
        dp[i][3] = tm + (2 if a == 0 else a % 2)
        tm = min(tm, dp[i - 1][4])
        dp[i][4] = tm + a
    
    return min(dp[L])


print(solve())

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
L=int(input())
b=[0]*5
a=[0]*5
for i in range(L):
    n=int(input())
    a[0]=b[0]+n
    a[1]=min(b[0],b[1])+n%2
    a[2]=min(b[0],b[1],b[2])+(not n%2)
    a[3]=min(b[0],b[1],b[2],b[3])+n%2
    a[4]=min(b[0],b[1],b[2],b[3],b[4])+n
    if not n:
        a[1]+=2
        a[3]+=2
    b=a.copy()
print(min(a))

Solution (Python):
import itertools

l = int(input())
a = [int(input()) for _ in range(l)]

e_cs = [int(not (v % 2)) for v in a]
o_cs = [2 if v == 0 else v % 2 for v in a]

cs = [0] + list(itertools.accumulate(a))
cost = [a, o_cs, e_cs, o_cs, a]















dp = [[None] * 5 for _ in range(l + 1)]
dp[l] = [0] * 5

for i in reversed(range(l)):
    for t in reversed(range(5)):
        if t == 4:
            dp[i][t] = cs[l] - cs[i]
            continue
        dp[i][t] = min(dp[i + 1][t] + cost[t][i], dp[i][t + 1])

print(dp[0][0])

Solution (Python):
import itertools

l = int(input())
a = [int(input()) for _ in range(l)]

e_cs = [int(not (v % 2)) for v in a]
o_cs = [2 if v == 0 else v % 2 for v in a]

cs = [0] + list(itertools.accumulate(a))
cost = [a, o_cs, e_cs, o_cs, a]















dp = [[None] * 5 for _ in range(l + 1)]
dp[l] = [0] * 5

for i in reversed(range(l)):
    for t in reversed(range(5)):
        if t == 4:
            dp[i][t] = cs[l] - cs[i]
            continue
        dp[i][t] = min(dp[i + 1][t] + cost[t][i], dp[i][t + 1])

print(dp[0][0])

Solution (Python):
n = int(input())
l = [int(input()) for _ in range(n)]
dp = [[0]*5 for _ in range(n+1)]
for i in range(n):
  dp[i+1][0] = dp[i][0] + l[i]
  dp[i+1][1] = min(dp[i][:2]) + (l[i] % 2 if l[i] else 2)
  dp[i+1][2] = min(dp[i][:3]) + (l[i] + 1) % 2
  dp[i+1][3] = min(dp[i][:4]) + (l[i] % 2 if l[i] else 2)
  dp[i+1][4] = min(dp[i][:5]) + l[i]
print(min(dp[n]))

Solution (Python):
import sys
input = sys.stdin.readline

L = int(input())
A = [int(input()) for _ in range(L)]
dpl = [[10**18]*2 for _ in range(L+1)]
dpl[0][1] = 0
acc = 0

for i in range(1, L+1):
    dpl[i][0] = min(dpl[i-1][0], dpl[i-1][1])+(1 if A[i-1]%2==0 else 0)
    acc += A[i-1]
    dpl[i][1] = acc
    
    if A[i-1]%2==0:
        if A[i-1]>=2:
            dpl[i][1] = min(dpl[i][1], dpl[i-1][1])
        else:
            dpl[i][1] = min(dpl[i][1], dpl[i-1][1]+2)
    else:
        dpl[i][1] = min(dpl[i][1], dpl[i-1][1]+1)
    
acc = 0
dpr = [[10**18]*2 for _ in range(L+1)]
dpr[L][1] = 0

for i in range(L-1, -1, -1):
    dpr[i][0] = min(dpr[i+1][0], dpr[i+1][1])+(1 if A[i]%2==0 else 0)
    acc += A[i]
    dpr[i][1] = acc
    
    if A[i]%2==0:
        if A[i]>=2:
            dpr[i][1] = min(dpr[i][1], dpr[i+1][1])
        else:
            dpr[i][1] = min(dpr[i][1], dpr[i+1][1]+2)
    else:
        dpr[i][1] = min(dpr[i][1], dpr[i+1][1]+1)

ans = 10**18

for i in range(L+1):
    ans = min(ans, dpl[i][0]+dpr[i][1], dpl[i][1]+dpr[i][0], dpl[i][1]+dpr[i][1])

print(ans)

Solution (Python):
n  = int(input())
a = [int(input()) for i in range(n)]


dp = [[0] * (5) for i in range(n + 1)]
for i in range(n):
    dp[i + 1][0] = dp[i][0] + a[i]

    dp[i + 1][1] = min(dp[i][0:2]) + (a[i] % 2)
    if a[i] == 0:
        dp[i + 1][1] += 2
        
    dp[i + 1][2] = min(dp[i][0:3]) + (a[i] + 1) % 2
    
    dp[i + 1][3] = min(dp[i][0:4]) + (a[i] % 2)
    if a[i] == 0:
        dp[i + 1][3] += 2
        
    dp[i + 1][4] = min(dp[i][0:5]) + a[i]

print(min(dp[-1]))

Solution (Python):
def main():
    from itertools import accumulate as ac
    n = int(input())
    a = [int(input()) for _ in [0]*n]
    a_ac = [0]+list(ac(a))
    s = a_ac[-1]

    dp0 = [0]*(n+1)
    dp1 = [0]*(n+1)
    dp2 = [0]*(n+1)
    dp3 = [0]*(n+1)

    for i in range(1, n+1):
        p = dp0[i-1]
        q = dp1[i-1]
        ai = a[i-1]
        dp0[i] = min(p+((ai+1) % 2), q+(ai % 2 if ai > 0 else 2), a_ac[i])
        dp1[i] = min(q+(ai % 2 if ai > 0 else 2), a_ac[i])

    for i in range(n-1, -1, -1):
        p = dp2[i+1]
        q = dp3[i+1]
        ai = a[i]
        dp2[i] = min(p+((ai+1) % 2), q+(ai % 2 if ai > 0 else 2), s-a_ac[i])
        dp3[i] = min(q+(ai % 2 if ai > 0 else 2), s-a_ac[i])

    dp_l = [min(i, j) for i, j in zip(dp0, dp1)]
    dp_r = [min(i, j) for i, j in zip(dp2, dp3)]
    print(min([i+j for i, j in zip(dp_l, dp_r)]))


main()

Solution (Python):
L = int(input())
dp = [[0]*5 for i in range(L+1)]
for i in range(L):
    x = int(input())
    c = [x, x%2 if x else 2, 1-x%2, x%2 if x else 2, x]
    for j in range(5):
        dp[i+1][j] = 10**18
        for k in range(j+1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][k]+c[j])
print(min(dp[-1]))

Solution (Python):
L = int(input())
A = [int(input()) for _ in range(L)]

def cost(k, a):
    if k == 0 or k == 4:
        return a

    if a % 2:
        a = 1
    elif a >= 2:
        a = 2

    if k == 1 or k == 3:
        return 2 - a

    return 1 - a % 2

dp = [[10**18] * 5 for _ in range(L + 1)]
dp[0][0] = 0

for i, a in enumerate(A, start=1):
    for j in range(5):
        for k in range(j, 5):
            b = dp[i - 1][j] + cost(k, a)
            if dp[i][k] > b:
                dp[i][k] = b

ans = min(dp[L])
print(ans)

Solution (Python):
L = int(input())
B = [int(input()) for _ in range(L)]

A = []
for b in B:
    if b % 2:
        A.append(1)
    else:
        A.append(0 if b == 0 else 2)

dpLBack = [10**10] * (L + 1)
dpLBack[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[i - 1]
    dpLBack[i] = min(dpLBack[i - 1] + 2 - a, cnt)

dpL = [10**10] * (L + 1)
dpL[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[i - 1]
    dpL[i] = min(dpL[i - 1] + (a != 1), dpLBack[i - 1] + (a == 0), cnt)

dpRBack = [10**10] * (L + 1)
dpRBack[0] = 0
cnt = 0
for i, a in enumerate(A[:: -1], start=1):
    cnt += B[-i]
    dpRBack[i] = min(dpRBack[i - 1] + 2 - a, cnt)

dpR = [10**10] * (L + 1)
dpR[0] = 0
cnt = 0
for i, a in enumerate(A[:: -1], start=1):
    cnt += B[-i]
    dpR[i] = min(dpR[i - 1] + (a != 1), dpRBack[i - 1] + (a == 0), cnt)

dpR = dpR[:: -1]
dpRBack = dpRBack[::-1]

ans = min(dpL[L], dpR[0])
for mid in range(L + 1):
    ans = min(ans, dpL[mid] + dpRBack[mid], dpLBack[mid] + dpR[mid], dpLBack[mid] + dpRBack[mid])

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = [0] * N
dp = [[0] * 5 for _ in range(N + 1)]
for i in range(N): a[i] = int(input())
for i in range(N + 1):
  for j in range(5): dp[i][j] = 10 ** 15

dp[0][0] = 0
for i in range(N):
  for j in range(5):
    for k in range(j, 5):
      w = a[i]
      if k % 2:
        if a[i] > 0: w = a[i] % 2
        else: w = 2
      elif k == 2: w = int(a[i] % 2 == 0)
      dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + w)
print(min(dp[-1]))

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

"""
状態をそのままdpのインデックスとする。
https://drken1215.hatenablog.com/entry/2019/02/10/014800
"""

def solve():
    def cost(k,i):
        ai = a[i]
        if k == 0:
            return ai
        elif k == 1:
            if ai == 0:
                return 2
            return ai&1
        elif k == 2:
            return 1-(ai&1)
        elif k == 3:
            if ai == 0:
                return 2
            return ai&1
        else:
            return ai

    l = I()
    a = IR(l)
    dp = [[float("inf")]*5 for i in range(l)]
    for i in range(5):
        dp[0][i] = cost(i,0)
    for i in range(l-1):
        ni = i+1
        for j in range(5):
            for k in range(j,5):
                c = cost(k,ni)
                nd = dp[i][j]+c
                if nd < dp[ni][k]:
                    dp[ni][k] = nd
    print(min(dp[l-1]))
    return


if __name__ == "__main__":
    solve()

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d

startとGoalを決めると、その間は奇数回、それ以外は偶数回通ることとなる
また、始点と終点は交換可能なので、始点が左にある方としてよい

始点・終点間は最小１で、好きな位置を2ずつ増やすことが可能
始点から左、終点より右は0があればそれ以降先は全て0にせざるを得ない
それ以外は2,4,6…と2ずつ好きに増やすことが可能

→大体情報が出そろってきた

もし終点と始点が全探索可能だとしたら？
始点より左の最適化 = 終点より右はどうするんだ？
→切れ目を全探索すれば行ける　始点・終点間は自明

高速化→dpだろうなぁ
フェーズごとに分ける

左のずっと0フェーズ→偶数フェーズ→(始点)→奇数フェーズ→(終点)→偶数フェーズ→0フェーズ
の5段階ごとに最小値を持っておいてあげればよい
あとは適当にdp(フェーズは戻っちゃだめだけど飛ばしても良いことに注意)
→解けた！！！
"""

dp = [0] * 5

L = int(input())

for i in range(L):

    ndp = [float("inf")] * 5

    A = int(input())

    ndp[0] = dp[0] + A

    if A == 0:
        D = 2
    else:
        D = A % 2
    ndp[1] = min(dp[0],dp[1]) + D
    ndp[2] = min(dp[0],dp[1],dp[2]) + (A+1)%2
    ndp[3] = min(dp[0],dp[1],dp[2],dp[3]) + D
    ndp[4] = min(dp) + A

    dp = ndp

print (min(dp))

Solution (Python):
L = int(input())
A = [int(input()) for _ in range(L)]

dp = [0] * 5
for a in A :
  ndp = [0] * 5
  ndp[0] = dp[0] + a
  ndp[1] = min(dp[0:2]) + a % 2
  ndp[2] = min(dp[0:3]) + (a + 1) % 2
  ndp[3] = min(dp[0:4]) + a % 2
  ndp[4] = min(dp[0:5]) + a
  
  if a == 0 : 
    ndp[1] += 2
    ndp[3] += 2
    
  dp = ndp
  
print(min(dp))

Solution (Python):
l=int(input())
dp=[0]*5
for i in range(l):
	a,b,c,d,e,f=dp+[int(input())]
	p=int(f==0)*2
	dp=[a+f,min(a,b)+f%2+p,min(a,b,c)+(f+1)%2,min(b,c,d)+f%2+p,min(b,c,d,e)+f]
print(min(dp))

Solution (Python):
l=int(input())
A=[int(input())for _ in range(l)]
dp=[0]*5
for i in range(l):
	a,b,c,d,e,f=dp+[A[i]]
	p=int(f==0)*2
	dp=[a+f,min(a,b)+f%2+p,min(a,b,c)+(f+1)%2,min(b,c,d)+f%2+p,min(b,c,d,e)+f]
print(min(dp))

Solution (Python):
l=int(input())
A=[int(input())for _ in range(l)]
dp=[0]*5
for i in range(l):
    a,b,c,d,e,f=dp+[A[i]]
    p=int(f==0)*2
    dp=[a+f,min(a,b)+f%2+p,min(a,b,c)+(f+1)%2,min(b,c,d)+f%2+p,min(b,c,d,e)+f]
print(min(dp))

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
b = [0]*n
for i in range(n):
  if a[i]%2:
    b[i] = 1
  elif a[i]:
    b[i] = 2
DP = [[10**18 for i in range(5)] for j in range(n+1)]
for i in range(5):
    DP[0][i] = 0
for i in range(1,n+1):
  for j in range(5):
    for k in range(j,5):
      if k == 0 or k == 4:
        DP[i][k] = min(DP[i][k],DP[i-1][j]+a[i-1])
      elif k == 1 or k == 3:
        DP[i][k] = min(DP[i][k],DP[i-1][j]+abs(b[i-1]-2))
      else:
        DP[i][k] = min(DP[i][k],DP[i-1][j]+abs(b[i-1]-1))
print(min(DP[n]))

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
b = [0]*n
for i in range(n):
  if a[i]%2:
    b[i] = 1
  elif a[i]:
    b[i] = 2
a.append(0)
b.append(0)
n += 1
DP = [[[10**18 for i in range(3)] for j in range(3)] for k in range(n+1)]
for i in range(3):
  for j in range(3):
    DP[0][i][j] = 0
for i in range(1,n+1):
  for k in (0,2):
    DP[i][0][k] = min(DP[i][0][k],DP[i-1][0][k]+abs(a[i-1]))
  for l in (1,2):
    DP[i][0][2] = min(DP[i][0][2],DP[i-1][l][2]+abs(a[i-1]))
  DP[i][0][2] = min(DP[i][0][2],DP[i-1][2][1]+abs(a[i-1]))

  DP[i][1][2] = min(DP[i][1][2],DP[i-1][0][0]+abs(b[i-1]-1))
  DP[i][1][2] = min(DP[i][1][2],DP[i-1][1][2]+abs(b[i-1]-1))
  DP[i][1][2] = min(DP[i][1][2],DP[i-1][2][1]+abs(b[i-1]-1))

  for k in (1,2):
    DP[i][2][k] = min(DP[i][2][k],DP[i-1][2][k]+abs(b[i-1]-2))
  DP[i][2][2] = min(DP[i][2][2],DP[i-1][1][2]+abs(b[i-1]-2))
  DP[i][2][1] = min(DP[i][2][1],DP[i-1][0][0]+abs(b[i-1]-2))
print(min(*DP[n][0]))

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np

N = int(input())
A = [int(input()) for _ in range(N)]

p1 = 0
p2 = 0
P1 = [0]
P2 = [0]
for a in A:
    if a == 0:
        p1 -= 2
        p2 += 1
    elif a % 2 == 0:
        p2 -= 1
    elif a % 2 == 1:
        p1 -= 1
        p2 += 1
    p1 += a
    P1.append(p1)
    P2.append(p2)

dp = [P1[N], P1[N]+P2[N], -P1[N], 0]

for i in reversed(range(N)):
    dp[0] = max(dp[0], P1[i])
    dp[1] = max(dp[1], P2[i]+dp[0])
    dp[2] = min(dp[2], P2[i]-dp[1])
    dp[3] = min(dp[3], P1[i]+dp[2])

print(dp[3]+sum(A))

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]

p1 = 0
p2 = 0
P1 = [0]
P2 = [0]
for a in A:
    if a == 0:
        p1 -= 2
        p2 += 1
    elif a % 2 == 0:
        p2 -= 1
    elif a % 2 == 1:
        p1 -= 1
        p2 += 1
    p1 += a
    P1.append(p1)
    P2.append(p2)

S = sum(A)
dp = [[0, 0, 0, 0] for _ in range(N+1)]

dp[N] = [P1[N], P1[N]+P2[N], -P1[N], 0]

for i in reversed(range(N)):
    dp[i][0] = max(dp[i+1][0], P1[i])
    dp[i][1] = max(dp[i+1][1], P2[i]+dp[i][0])
    dp[i][2] = min(dp[i+1][2], P2[i]-dp[i][1])
    dp[i][3] = min(dp[i+1][3], P1[i]+dp[i][2])

print(dp[0][3]+S)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

L = int(input())
A = [0] * L
for i in range(L):
    A[i] = int(input())

dp = [[0 for _ in range(5)] for _ in range(L+1)]
dp[0][0] = 0
for i in range(L):
    if A[i] != 0:
        dp[i+1][0] = dp[i][0] + A[i]
        dp[i+1][1] = min(dp[i][:2]) + A[i] % 2
        dp[i+1][2] = min(dp[i][:3]) + (A[i]+1) % 2
        dp[i+1][3] = min(dp[i][:4]) + A[i] % 2
        dp[i+1][4] = min(dp[i]) + A[i]
    else:
        dp[i + 1][0] = dp[i][0] + A[i]
        dp[i + 1][1] = min(dp[i][:2]) + 2
        dp[i + 1][2] = min(dp[i][:3]) + 1
        dp[i + 1][3] = min(dp[i][:4]) + 2
        dp[i + 1][4] = min(dp[i]) + A[i]
print(min(dp[-1]))

Solution (Python):
import sys
import math
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))


dp = [[n] * (n + 1) for _ in range(5)]
for i in range(5):
    dp[i][0] = 0
for i, item in enumerate(a):
    if item != 0:
        odd_cost = (item % 2 == 1)
        even_cost = (item % 2 == 0)
        
        dp[0][i+1] = min(dp[0][i+1], dp[0][i] + item)
        dp[1][i+1] = min(dp[1][i+1], dp[0][i] + odd_cost)
        dp[2][i+1] = min(dp[2][i+1], dp[0][i] + even_cost)
        dp[3][i+1] = min(dp[3][i+1], dp[0][i] + odd_cost)
        dp[4][i+1] = min(dp[4][i+1], dp[0][i] + item)
        
        dp[1][i+1] = min(dp[1][i+1], dp[1][i] + odd_cost)
        dp[2][i+1] = min(dp[2][i+1], dp[1][i] + even_cost)
        dp[3][i+1] = min(dp[3][i+1], dp[1][i] + odd_cost)
        dp[4][i+1] = min(dp[4][i+1], dp[1][i] + item)
        
        dp[2][i+1] = min(dp[2][i+1], dp[2][i] + even_cost)
        dp[3][i+1] = min(dp[3][i+1], dp[2][i] + odd_cost)
        dp[4][i+1] = min(dp[4][i+1], dp[2][i] + item)
        
        dp[3][i+1] = min(dp[3][i+1], dp[3][i] + odd_cost)
        dp[4][i+1] = min(dp[4][i+1], dp[3][i] + item)
        
        dp[4][i+1] = min(dp[4][i+1], dp[4][i] + item)
    else:
        
        dp[0][i+1] = min(dp[0][i+1], dp[0][i])
        dp[1][i+1] = min(dp[1][i+1], dp[0][i] + 2)
        dp[2][i+1] = min(dp[2][i+1], dp[0][i] + 1)
        dp[3][i+1] = min(dp[3][i+1], dp[0][i] + 2)
        dp[4][i+1] = min(dp[4][i+1], dp[0][i])
        
        dp[1][i+1] = min(dp[1][i+1], dp[1][i] + 2)
        dp[2][i+1] = min(dp[2][i+1], dp[1][i] + 1)
        dp[3][i+1] = min(dp[3][i+1], dp[1][i] + 2)
        dp[4][i+1] = min(dp[4][i+1], dp[1][i])
        
        dp[2][i+1] = min(dp[2][i+1], dp[2][i] + 1)
        dp[3][i+1] = min(dp[3][i+1], dp[2][i] + 2)
        dp[4][i+1] = min(dp[4][i+1], dp[2][i])
        
        dp[3][i+1] = min(dp[3][i+1], dp[3][i] + 2)
        dp[4][i+1] = min(dp[4][i+1], dp[3][i])
        
        dp[4][i+1] = min(dp[4][i+1], dp[4][i])

ans = n
for line in dp:
    ans = min(ans, line[n])
print(ans)

Solution (Python):
import os
import sys

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

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


def cumsum(li):
    ret = []
    sum = 0
    for i in li:
        sum += i
        ret.append(sum)
    return ret



N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]







dp = [[0] * 5 for _ in range(N)]
for i, a in enumerate(cumsum(A)):
    dp[i][0] = a
dp[0][1] = int((A[0] % 2 != 0) + (A[0] == 0) * 2)
dp[0][2] = int(A[0] % 2 != 1)
dp[0][3] = int((A[0] % 2 != 0) + (A[0] == 0) * 2)
dp[0][4] = A[0]

for i in range(1, N):
    dp[i][ 1] = min(dp[i - 1][ :1 + 1]) + int((A[i] % 2 != 0) + (A[i] == 0) * 2)
    dp[i][ 2] = min(dp[i - 1][ :2 + 1]) + int(A[i] % 2 != 1)
    dp[i][ 3] = min(dp[i - 1][ :3 + 1]) + int((A[i] % 2 != 0) + (A[i] == 0) * 2)
    dp[i][ 4] = min(dp[i - 1][ :4 + 1]) + A[i]
print(min(dp[-1]))

Solution (Python):
def main():
    L, *A = map(int, open(0))

    EO = [(2, 1), (1, 0), (0, 1)]

    dp = [0] * 5

    for a in A:
        e, o = EO[(a - 1) % 2 + 1 if a else 0]

        dp[0] += a
        dp[1] = min(dp[0], dp[1] + e)
        dp[2] = min(dp[1], dp[2] + o)
        dp[3] = min(dp[2], dp[3] + e)
        dp[4] = min(dp[3], dp[4] + a)

    print(min(dp))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    L, *A = map(int, open(0))

    D = [(2, 1), (1, 0), (0, 1)]

    s0 = s1 = s2 = s3 = s4 = 0

    for a in A:
        e, o = D[(a - 1) % 2 + 1 if a else 0]

        s0 += a
        s1 = min(s0, s1 + e)
        s2 = min(s1, s2 + o)
        s3 = min(s2, s3 + e)
        s4 = min(s3, s4 + a)

    print(min(s0, s1, s2, s3, s4))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    L, *A = map(int, open(0))

    D = [(2, 1), (1, 0), (0, 1)]

    s0 = s1 = s2 = s3 = s4 = 0

    for a in A:
        e, o = D[(a - 1) % 2 + 1 if a else 0]

        s0 += a
        s1 = s0 if s0 < s1 + e else s1 + e
        s2 = s1 if s1 < s2 + o else s2 + o
        s3 = s2 if s2 < s3 + e else s3 + e
        s4 = s3 if s3 < s4 + a else s4 + a

    print(min(s0, s1, s2, s3, s4))

if __name__ == '__main__':
    main()

Solution (Python):
L, *A = map(int, open(0))

D = [(2, 1), (1, 0), (0, 1)]

s0 = s1 = s2 = s3 = s4 = 0

for a in A:
    e, o = D[(a - 1) % 2 + 1 if a else 0]

    s0 += a
    s1 = s0 if s0 < s1 + e else s1 + e
    s2 = s1 if s1 < s2 + o else s2 + o
    s3 = s2 if s2 < s3 + e else s3 + e
    s4 = s3 if s3 < s4 + a else s4 + a

print(min(s0, s1, s2, s3, s4))

Solution (Python):
L, *A = map(int, open(0))

D = [(2, 1), (1, 0), (0, 1)]

s0 = s1 = s2 = s3 = s4 = 0

for a in A:
    e, o = D[(a - 1) % 2 + 1 if a else 0]

    s0 += a
    s1 = min(s0, s1 + e)
    s2 = min(s1, s2 + o)
    s3 = min(s2, s3 + e)
    s4 = min(s3, s4 + a)

print(min(s0, s1, s2, s3, s4))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

"""
0,0,0,...,0,ev,ev,ev,,,ev,od,od,,,od,ev,ev,,,,ev,0,0,0,0,0
"""

L = int(input())
A = (int(x) for x in sys.stdin.read().split())


a,b,c,d,e = 0,0,0,0,0
for x in A:
    ev_score = 1 if x&1 else (0 if x > 0 else 2)
    od_score = 1-(x&1)
    a1 = a + x
    b1 = min(a,b) + ev_score
    c1 = min(a,b,c) + od_score
    d1 = min(c,d) + ev_score
    e1 = min(b,c,d,e) + x
    a,b,c,d,e = a1,b1,c1,d1,e1

answer = min(a,b,c,d,e)
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline

def main():
  l = int(input())
  dp = [[float('inf') for _ in range(l+1)] for _ in range(5)]
  dp[0][0] = 0
  for i in range(l):
    a = int(input())
    for j in range(5):
      for k in range(j, 5):
        cost = a
        if k == 1 or k == 3:
          if a % 2 == 0 and a > 0:
            cost = 0
          elif a > 0:
            cost = 1
          else:
            cost = 2
        elif k == 2:
          if a % 2 == 1:
            cost = 0
          else:
            cost = 1
        if dp[k][i+1] > dp[j][i] + cost:
          dp[k][i+1] = dp[j][i] + cost
  print(min([dpp[-1] for dpp in dp]))


if __name__ == '__main__':
  main()

Solution (Python):
from itertools import accumulate

L = int(input())
A = [int(input()) for _ in range(L)]
two_way_A = [a%2 if a>0 else 2 for a in A]
one_way_A = [(a+1)%2 for a in A]

dp = [[0]*L for _ in range(5)]
transition = [A, two_way_A, one_way_A, two_way_A, A] 

dp[0] = list(accumulate(A))
for i in range(1,5):
  dp[i][0] = min(transition[i][0], dp[i-1][0])
  for j in range(1,L):
    dp[i][j] = min(min(dp[i-1][j-1],dp[i][j-1])+transition[i][j], dp[i-1][j])

print(dp[-1][-1])

Solution (Python):
L = int(input())
A = [int(input()) for _ in range(L)]

dp = [0] * (L + 1)
dp[0] = [0] * 5

for i in range(L):
  dp[i + 1] = [0] * 5
  dp[i + 1][0] = dp[i][0] + A[i]
  cost1 = A[i] % 2 if A[i] != 0 else 2
  dp[i + 1][1] = min([dp[i][0] + cost1, dp[i][1] + cost1])
  cost2 = (A[i] + 1) % 2
  dp[i + 1][2] = min([dp[i][0] + cost2, dp[i][1] + cost2, dp[i][2] + cost2])
  cost3 = A[i] % 2 if A[i] != 0 else 2
  dp[i + 1][3] = min([dp[i][0] + cost3, dp[i][1] + cost3, dp[i][2] + cost3, dp[i][3] + cost3])
  dp[i + 1][4] = min([dp[i][0] + A[i], dp[i][1] + A[i], dp[i][2] + A[i], dp[i][3] + A[i], dp[i][4] + A[i]])

print(min(dp[L]))