Problem:


Score : 300 points

Problem Statement

You are given an integer sequence of length N. The i-th term in the sequence is a_i.
In one operation, you can select a term and either increment or decrement it by one.

At least how many operations are necessary to satisfy the following conditions?

For every i (1≤i≤n), the sum of the terms from the 1-st through i-th term is not zero.

For every i (1≤i≤n-1), the sign of the sum of the terms from the 1-st through i-th term, is different from the sign of the sum of the terms from the 1-st through (i+1)-th term.

Constraints

2 ≤ n ≤ 10^5

|a_i| ≤ 10^9

Each a_i is an integer.

Input

Input is given from Standard Input in the following format:

n
a_1 a_2 ... a_n

Output

Print the minimum necessary count of operations.

Sample Input 1

4
1 -3 1 0

Sample Output 1

4

For example, the given sequence can be transformed into 1, -2, 2, -2 by four operations. The sums of the first one, two, three and four terms are 1, -1, 1 and -1, respectively, which satisfy the conditions.

Sample Input 2

5
3 -6 4 -5 7

Sample Output 2

0

The given sequence already satisfies the conditions.

Sample Input 3

6
-1 4 3 2 -5 4

Sample Output 3

8



Sample input:
4
1 -3 1 0


Sample output:
4

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=list(map(int,readline().split()))

    s=[a[0]]*n
    for i in range(1,n):
        s[i]=s[i-1]+a[i]

    flag=True
    #1,-1,...
    for i in range(n):
        if i%2==0:
            if s[i]<=0:
                flag=False
                break
        else:
            if s[i]>=0:
                flag=False
                break

    if flag:
        print(0)
    else:  #-1,1,...
        flag=True
        for i in range(n):
            if i%2==0:
                if s[i]>=0:
                    flag=False
                    break
            else:
                if s[i]<=0:
                    flag=False
                    break
        if flag:
            print(0)
        else:
            cnt1=0
            s1=s[:]
            f1=0
            #1,-1,...
            for i in range(n):
                if i%2==0:
                    if s1[i]+f1<=0:
                        cnt1+=abs(1-s1[i]-f1)
                        f1+=1-s1[i]-f1
                else:
                    if s1[i]+f1>=0:
                        cnt1+=abs(-1-s1[i]-f1)
                        f1+=-1-s1[i]-f1
            
            cnt2=0
            s2=s[:]
            f2=0
            #-1,1,...
            for i in range(n):
                if i%2==0:
                    if s2[i]+f2>=0:
                        cnt2+=abs(-1-s2[i]-f2)
                        f2+=-1-s2[i]-f2
                else:
                    if s2[i]+f2<=0:
                        cnt2+=abs(1-s2[i]-f2)
                        f2+=1-s2[i]-f2
            print(min(cnt1,cnt2))

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

def sol(S):
    ret = 0
    for a in A[1:]:
        b = a
        if S * (S + b) > 0:
            b = (abs(S) + 1) * (1 if S < 0 else -1)
        if S + b == 0:
            b = b - 1 if S < 0 else b + 1
        ret += abs(b - a)
        S += b
    return ret

if A[0] == 0:
    ans = min(sol(1), sol(-1)) + 1
else:
    ans = min(sol(A[0]), sol(-1 if A[0] > 0 else 1) + abs(A[0]) + 1)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
a = list(map(int, readline().split()))
if a[0] > 0:
    cnt2 = a[0] + 1
    now2 = -1
    cnt1 = 0
    now1 = a[0]
elif a[0] == 0:
    cnt2 = 1
    now2 = -1
    cnt1 = 1
    now1 = 1
else:
    cnt2 = 0
    now2 = a[0]
    cnt1 = -a[0] + 1
    now1 = 1
for i, aa in enumerate(a[1:]):
    if i % 2 == 0:
        if aa + now2 > 0:
            now2 += aa
        else:
            cnt2 += abs(now2 + aa) + 1
            now2 = 1
        if now1 + aa < 0:
            now1 += aa
        else:
            cnt1 += now1 + aa + 1
            now1 = -1
    else:
        if aa + now1 > 0:
            now1 += aa
        else:
            cnt1 += abs(now1 + aa) + 1
            now1 = 1
        if now2 + aa < 0:
            now2 += aa
        else:
            cnt2 += now2 + aa + 1
            now2 = -1
print(min(cnt1, cnt2))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
res = max(0, -a[0] + 1)
sm = 1
if a[0] >= 1:
  res = 0
  sm = a[0]
#print(res, sm)
for i in range(1, N):
  if sm > 0:
    res += max(-1, a[i] + sm) + 1
    sm = min(-1, sm + a[i])
  else:
    res += -min(1, sm + a[i]) + 1
    sm = max(1, sm + a[i])
  #print(res, sm)
res2 = max(0, a[0] + 1)
sm = -1
if a[0] <= -1:
  res2 = 0
  sm = a[0]
for i in range(1, N):
  if sm > 0:
    res2 += max(-1, a[i] + sm) + 1
    sm = min(-1, sm + a[i])
  else:
    res2 += -min(1, sm + a[i]) + 1
    sm = max(1, sm + a[i])
  #print(res2, sm)
#print(res, res2)
print(min(res, res2))

Submission status: Accepted

Solution code:
import sys
from collections import Counter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
a=lmp()
s=0
ans1=0
ans2=0
for i in range(n):
    if i%2==0:
        s+=a[i]
        if s>=0:
            ans1+=s-(-1)
            s=-1
    else:
        s+=a[i]
        if s<=0:
            ans1+=1-s
            s=1

s=0
for i in range(n):
    if i%2==1:
        s+=a[i]
        if s>=0:
            ans2+=s-(-1)
            s=-1
    else:
        s+=a[i]
        if s<=0:
            ans2+=1-s
            s=1
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = inpl()
now = 0
res = INF
cnt = 0
for i in range(n):
    now += a[i]
    if i%2 == 0:
        if now <= 0:
            cnt += 1-now
            now = 1
    else:
        if now >= 0:
            cnt += now+1
            now = -1
    # print(i,now,cnt)
res = min(res,cnt)
now = 0
cnt = 0
for i in range(n):
    now += a[i]
    if i%2:
        if now <= 0:
            cnt += -now + 1
            now = 1
    else:
        if now >= 0:
            cnt += now + 1
            now = -1
    # print(i,now,cnt)    
res = min(res,cnt)
print(res)

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))

ans = 10 ** 18


def calc(flag):
    total = 0
    count = 0
    for a in A:
        if flag:
            if total + a > 0:
                total += a
            else:
                count += 1 - (total + a)
                total = 1
            flag = False
        else:
            if total + a < 0:
                total += a
            else:
                count += (total + a) - (-1)
                total = -1
            flag = True
    return count

print (min(calc(True), calc(False)))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
acc = [a[0]]
for i in range(1, n):
    acc.append(acc[-1] + a[i])

res = 10 ** 100

def f(fir):
    prv_pos = fir > 0
    margin = fir - a[0]
    ret = abs(margin)
    for i in range(1, n):
        cur = margin + acc[i]
        if prv_pos and cur < 0:
            prv_pos = not prv_pos
            continue
        if not prv_pos and cur > 0:
            prv_pos = not prv_pos
            continue
        if prv_pos:
            need = -1
            sa = need - cur
            margin += sa
            ret += abs(sa)
        else:
            need = 1
            sa = need - cur
            margin += sa
            ret += abs(sa)
        prv_pos = not prv_pos
    return ret


res = min(res, f(1))
res = min(res, f(-1))
if a[0] != 0:
    res = min(res, f(a[0]))
print(res)

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = list(map(int,input().split()))
# + - + - のパターン
ans1 = 0
acum = 0
for i in range(n):
  pre_plus = i % 2 == 0
  acum += A[i]
  if (pre_plus and acum < 0) or (not pre_plus and acum > 0):pass
  elif not pre_plus:
    ans1 += 1-acum
    acum = 1
  else:
    ans1 += abs(acum-(-1))
    acum = -1
  # print(i,acum,ans1)

# + - + - のパターンnogyaku
ans2 = 0
pre_plus = 1
acum = 0
for i in range(n):
  pre_plus= i % 2 == 1
  acum += A[i]
  if (pre_plus and acum < 0) or (not pre_plus and acum > 0):pass
  elif not pre_plus:
    ans2 += 1-acum
    acum = 1
  else:
    ans2 += abs(acum-(-1))
    acum = -1

print(min(ans1,ans2))
# print(ans1,ans2)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import copy

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


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))

    # + - + - の順番
    S = 0
    cnt = 0
    for i in range(N):
        S += A[i]
        if i % 2 == 0:
            # +
            if S > 0:
                continue
            else:
                cnt += abs(S) + 1
                S += abs(S) + 1
        else:
            # -
            if S < 0:
                pass
            else:
                cnt += abs(S) + 1
                S -= abs(S) + 1
    ans = cnt

    # - + - +の順番
    S = 0
    cnt = 0
    for i in range(N):
        S += A[i]
        if i % 2 == 1:
            # +
            if S > 0:
                continue
            else:
                cnt += abs(S) + 1
                S += abs(S) + 1
        else:
            # -
            if S < 0:
                continue
            else:
                cnt += abs(S) + 1
                S -= abs(S) + 1

    if ans > cnt:
        ans = cnt
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    if A[0] == 0:
        answer = []
        for a in (1, -1):
            cnt = 1
            S = a
            for i in range(1, N):
                s = S + A[i]
                if A[i] == 0:
                    if S > 0:
                        cnt += S + 1
                        S = -1
                    else:
                        cnt += abs(S) + 1
                        S = 1
                else:
                    if s == 0:
                        if S < 0:
                            cnt += 1
                            S = 1
                        else:
                            cnt += 1
                            S = -1
                    else:
                        if S * s > 0:
                            if S < 0:
                                cnt += abs(s) + 1
                                S = 1
                            else:
                                cnt += s + 1
                                S = -1
                        else:
                            S = s
            answer.append(cnt)
        print(min(answer))
    else:
        if A[0] > 0:
            cnt1 = 0
            S1 = A[0]
            cnt2 = A[0] + 1
            S2 = -1
        else:
            cnt1 = 0
            S1 = A[0]
            cnt2 = abs(A[0]) + 1
            S2 = 1
        answer = []
        for cnt, S in [(cnt1, S1), (cnt2, S2)]:
            for i in range(1, N):
                s = S + A[i]
                if A[i] == 0:
                    if S > 0:
                        cnt += S + 1
                        S = -1
                    else:
                        cnt += abs(S) + 1
                        S = 1
                else:
                    if s == 0:
                        if S < 0:
                            cnt += 1
                            S = 1
                        else:
                            cnt += 1
                            S = -1
                    else:
                        if S * s > 0:
                            if S < 0:
                                cnt += abs(s) + 1
                                S = 1
                            else:
                                cnt += s + 1
                                S = -1
                        else:
                            S = s
            answer.append(cnt)
        print(min(answer))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def sign(x):
  if x<0:
    return -1
  elif x>0:
    return 1
  else:
    return 0
n = int(input())
a = list(map(int,input().split()))
a_sum_pn = 0
a_sum_np = 0
ans_pn = 0
ans_np = 0
flag = 1
for i in range(n):
  a_sum_pn += a[i]
  a_sum_np += a[i]
  if sign(a_sum_pn) != flag:
    ans_pn += abs(flag-a_sum_pn)
    a_sum_pn = flag
  if sign(a_sum_np) != -flag:
    ans_np += abs(-flag-a_sum_np)
    a_sum_np = -flag
  flag *= -1
print(min(ans_pn,ans_np))

Submission status: Accepted

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    n = int(_in[0])  # type:int
    a_arr = list(map(int,_in[1].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt0 = 0
    sum_ = 0
    for i in range(0,n):
        if i%2 == 0:
            if sum_+a_arr[i]<=0:
                cnt0 += 1-(sum_+a_arr[i])
                sum_ = 1
            else:
                sum_ = sum_+a_arr[i]
        else:
            if sum_+a_arr[i]>=0:
                cnt0 += 1+(sum_+a_arr[i])
                sum_ = -1
            else:
                sum_ = sum_+a_arr[i]
    cnt1 = 0
    sum_ = 0
    for i in range(0,n):
        if i%2 == 1:
            if sum_+a_arr[i]<=0:
                cnt1 += 1-(sum_+a_arr[i])
                sum_ = 1
            else:
                sum_ = sum_+a_arr[i]
        else:
            if sum_+a_arr[i]>=0:
                cnt1 += 1+(sum_+a_arr[i])
                sum_ = -1
            else:
                sum_ = sum_+a_arr[i]
    cnt = min(cnt0,cnt1)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
alist=list(map(int,input().split()))

cnt1=0
asum=0
#a0>0
for i in range(n):
  asum+=alist[i]
  if i%2==0:
    if asum<=0:
      cnt1+=1-asum
      asum+=1-asum
  else:
    if asum>=0:
      cnt1+=asum+1
      asum-=asum+1
      
cnt2=0
asum=0
#a0<0
for i in range(n):
  asum+=alist[i]
  if i%2==0:
    if asum>=0:
      cnt2+=asum+1
      asum-=asum+1
  else:
    if asum<=0:
      cnt2+=1-asum
      asum+=1-asum

#print(cnt1,cnt2)      
print(min(cnt1,cnt2))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, *a = map(int, read().split())
ans = float('inf')
for i in (-1, 1):
    cnt, now = 0, 0
    for aa in a:
        now += aa
        if now * i <= 0:
            cnt += abs(now - i)
            now = i
        i *= -1
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = list(map(int,input().split()))
arr = np.array(a)

# 奇数がプラス、偶数がマイナス
cost1 = 0
cum = 0
for i in range(n):
    cum += arr[i]
    tmp = abs(cum) + 1
    if i%2==1 and cum<=0: cost1 += tmp ; cum += tmp
    if i%2==0 and cum>=0: cost1 += tmp ; cum -= tmp

# 奇数がマイナス、偶数がプラス
cost2 = 0
cum = 0
for i in range(n):
    cum += arr[i]
    tmp = abs(cum) + 1
    if i%2==1 and cum>=0: cost2 += tmp ; cum -= tmp
    if i%2==0 and cum<=0: cost2 += tmp ; cum += tmp


ans = min(cost1, cost2)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
s1 = s2 =  0
#偶数番目までの和を正→ans1、奇数番目までの和を正→ans2
ans1 = ans2 = 0
#ans1について
for i in range(len(A)):
    s1 += A[i]
    if (i+1)%2==0:
        if s1>0:
            continue
        else:
            ans1+= abs(s1) + 1
            s1 = 1
    else:
        if s1<0:
            continue
        else:
            ans1 += abs(s1) +1
            s1 = -1
#ans2について
for i in range(len(A)):
    s2 += A[i]
    if (i+1)%2 == 0:
        if s2 <0:
            continue
        else:
            ans2 += abs(s2) + 1
            s2 = -1
    else:
        if s2 > 0:
            continue
        else:
            ans2 += abs(s2) + 1
            s2 = 1
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
key = 0
ans = 0
for i in range(n):
  sub = key + a[i]
  if i == 0 and sub == 0:
    ans += 1
    sub = 1
  if i != 0 and sub*key >= 0:
    if key > 0:
      ans += sub+1
      sub = -1
    else:
      ans += 1-sub
      sub = 1
  key = sub

ans2 = 0
key2 = 0
for i in range(n):
  sub = key2 + a[i]
  if i == 0:
    if sub == 0:
      ans2 += 1
      sub = -1
    elif sub > 0:
      ans2 += sub+1
      sub = -1
    else:
      ans2 += 1-sub
      sub = 1
  if i != 0 and sub*key2 >= 0:
    if key2 > 0:
      ans2 += sub+1
      sub = -1
    else:
      ans2 += 1-sub
      sub = 1
  key2 = sub
      
print(min([ans, ans2]))

Submission status: Accepted

Solution code:
n = int(input())
ns = list(map(int, input().split()))
sum_i = 0
cnt = 0
for i in range(n):
    sum_i += ns[i]
    if i % 2 == 0:
        if sum_i > 0:
            continue
        elif sum_i < 0:
            cnt += abs(sum_i) + 1
            sum_i = 1
        else:
            cnt += 1
            sum_i = 1
    else:
        if sum_i > 0:
            cnt += sum_i + 1
            sum_i = -1
        elif sum_i < 0:
            continue
        else:
            cnt += 1
            sum_i = -1
min_cnt = cnt
cnt = 0
sum_i = 0
for i in range(n):
    sum_i += ns[i]
    if (i+1) % 2 == 0:
        if sum_i > 0:
            continue
        elif sum_i < 0:
            cnt += abs(sum_i) + 1
            sum_i = 1
        else:
            cnt += 1
            sum_i = 1
    else:
        if sum_i > 0:
            cnt += sum_i + 1
            sum_i = -1
        elif sum_i < 0:
            continue
        else:
            cnt += 1
            sum_i = -1
print(min(min_cnt, cnt))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans1, ans2 = 0, 0
s = 0
plus = True
for i in range(n):
    if plus:
        if s + a[i] > 0:
            s += a[i]
        else:
            ans1 += abs(1 - (s + a[i]))
            s = 1
    if not plus:
        if s + a[i] < 0:
            s += a[i]
        else:
            ans1 += abs(-1 - (s + a[i]))
            s = -1
    plus = not plus

s = 0
plus = False
for i in range(n):
    if plus:
        if s + a[i] > 0:
            s += a[i]
        else:
            ans2 += abs(1 - (s + a[i]))
            s = 1
    if not plus:
        if s + a[i] < 0:
            s += a[i]
        else:
            ans2 += abs(-1 - (s + a[i]))
            s = -1
    plus = not plus
print(min(ans1, ans2))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

def main():
    N = int(readline())
    A = list(map(int, readline().rstrip().split()))
    for i in range(1, N):
        A[i] += A[i-1]
    cnt1, cnt2 = 0, 0
    ref1, ref2 = 0, 0
    for i, a in enumerate(A):
        if i % 2 == 0:
            if a <= ref1:
                cnt1 += ref1 - a + 1
                ref1 -= ref1 - a + 1
            if a >= ref2:
                cnt2 += a - ref2 + 1
                ref2 += a - ref2 + 1
        if i % 2 == 1:
            if a >= ref1:
                cnt1 += a - ref1 + 1
                ref1 += a - ref1 + 1
            if a <= ref2:
                cnt2 += ref2 - a + 1
                ref2 -= ref2 - a + 1

    print(min(cnt1, cnt2))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n  = int(input())
A = list(map(int,input().split()))
pal = [-1,1]
cnt = 10**18
for p in pal:
    s = 0
    tmp = 0
    prev = p
    for a in A:
        s+=a
        if s==0:
            tmp+=1
            s = prev
            prev*=-1
            continue
        if a==0:
            tmp +=abs(s)+1
            s = prev
            prev*=-1
            continue
        if s//abs(s) != prev:
            tmp+=abs(s)+1
            s = prev
        else:
            pass
        prev*=-1
    cnt = min(cnt,tmp)
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans1,ans2 = 0,0
sum1,sum2 = 0,0
for i in range(n):
    sum1 += a[i]
    if i%2 == 1 and sum1 >= 0:
        ans1 += sum1 + 1
        sum1 = -1
    elif i%2 == 0 and sum1 <= 0:
        ans1 += -sum1 + 1
        sum1 = 1
for i in range(n):
    sum2 += a[i]
    if i%2 == 0 and sum2 >= 0:
        ans2 += sum2 + 1
        sum2 = -1
    elif i%2 == 1 and sum2 <= 0:
        ans2 += -sum2 + 1
        sum2 = 1
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))

b = [0]*n
b[0]=a[0]
pt = 0
m = 0
ans1 = 0
ans2 = 0
for i in range(1,n):
    b[i]=b[i-1]+a[i]

for i in range(n):
    if i%2==0 and b[i]+m<=0:
        ans1+=1-b[i]-m
        m+=1-b[i]-m
    elif i%2==1 and b[i]+m>=0:
        ans1+=1+b[i]+m
        m+=-1-b[i]-m
m=0
for i in range(n):
    if i%2==1 and b[i]+m<=0:
        ans2+=1-b[i]-m
        m+=1-b[i]-m
    elif i%2==0 and b[i]+m>=0:
        ans2+=1+b[i]+m
        m+=-1-b[i]-m
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
import copy

n = int(input())
a = list(map(int,(input().split())))
s = [0]*n
s[0] = a[0]
for i in range(n-1):
    s[i+1] = s[i] + a[i+1]

s2 = copy.copy(s)
ans = []

# 最初を正とする場合
ans1 = 0
tmp = 0
for i in range(n):
    if i%2 == 0: #奇数項
        s[i] += tmp
        if s[i] <= 0:
            tmp += 1 - s[i]
            ans1 += 1 - s[i]
    else: #偶数項
        s[i] += tmp
        if s[i] >= 0:
            tmp -= s[i] + 1
            ans1 += s[i] + 1

s = s2
# 最初を負とする場合
ans2 = 0
tmp = 0
for i in range(n):
    if i%2 == 0: #奇数項
        s[i] += tmp
        if s[i] >= 0:
            tmp -= s[i] + 1
            ans2 += s[i] + 1
    else: #偶数項
        s[i] += tmp
        if s[i] <= 0:
            tmp += 1 - s[i]
            ans2 += 1 - s[i]

print(min(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans1,ans2 = 0,0
sum1,sum2 = 0,0
for i in range(n):
    sum1 += a[i]
    if i%2 == 1 and sum1 >= 0:
        ans1 += sum1 + 1
        sum1 = -1
    elif i%2 == 0 and sum1 <= 0:
        ans1 += -sum1 + 1
        sum1 = 1
for i in range(n):
    sum2 += a[i]
    if i%2 == 0 and sum2 >= 0:
        ans2 += sum2 + 1
        sum2 = -1
    elif i%2 == 1 and sum2 <= 0:
        ans2 += -sum2 + 1
        sum2 = 1
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

# 偶数番目(0-origin)を正とする場合
minA = 0
sumA = 0
for i in range(n):
	sumA += a[i]
	if i % 2 == 0:
		if sumA <= 0:
			minA += abs(sumA) + 1
			sumA += abs(sumA) + 1
	else:
		if sumA >= 0:
			minA += abs(sumA) + 1
			sumA -= abs(sumA) + 1

# 奇数番目(0-origin)を正とする場合
minB = 0
sumB = 0
for i in range(n):
	sumB += a[i]
	if i % 2 != 0:
		if sumB <= 0:
			minB += abs(sumB) + 1
			sumB += abs(sumB) + 1
	else:
		if sumB >= 0:
			minB += abs(sumB) + 1
			sumB -= abs(sumB) + 1

print(min(minA, minB))

Submission status: Accepted

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

n = int(input())
a = list( map(int, input().split()))

from itertools import accumulate
acc = a
acc = list(accumulate(acc))

def dfs(ind,prev,tmp,ans):
    if ind == n:
        return ans
    now = acc[ind]

    if prev > 0:
        if now + tmp >= 0:
            ans +=abs(now + tmp +1)
            tmp += -(now + tmp +1)
    elif prev < 0:
        if now + tmp <= 0:
            ans +=abs(now + tmp -1)
            tmp += -(now + tmp -1)

    return dfs(ind+1, now+tmp,tmp,ans)

ansM = dfs(0,-1,0,0)
ansP = dfs(0,+1,0,0)

print(min(ansM,ansP))

Submission status: Accepted

Solution code:


N = int(input())
A = list(map(int, input().split()))



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


# +-+-+-+-
ans1 = 0
tmp = [0] * N
for i in range(N):
    if i == 0:
        tmp[i] = A[i]
    else:
        tmp[i] = tmp[i-1] + A[i]

    if i % 2 == 0:
        if tmp[i] <= 0:
            ans1 += abs(tmp[i]) + 1
            tmp[i] = 1
    else:
        if tmp[i] >= 0:
            ans1 += abs(tmp[i]) + 1
            tmp[i] = -1

# -+-+-+-+
ans2 = 0
tmp = [0] * N
for i in range(N):
    if i == 0:
        tmp[i] = A[i]
    else:
        tmp[i] = tmp[i-1] + A[i]

    if i % 2 == 1:
        if tmp[i] <= 0:
            ans2 += abs(tmp[i]) + 1
            tmp[i] = 1
    else:
        if tmp[i] >= 0:
            ans2 += abs(tmp[i]) + 1
            tmp[i] = -1

print(min(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())

a = list(map(int, input().split()))

total = 0
ans_m = 0
ans_p = 0

hugo = 1
for i in range(n):
    total += a[i]
    if hugo == -1 and total <= 0:
        ans_p = ans_p + (1-total)
        total = 1
        hugo = 1
    elif hugo == -1 and total > 0:
        hugo = 1
    elif hugo == 1 and total >= 0:
        ans_p = ans_p + (1+total)
        total = -1
        hugo = -1
    elif hugo == 1 and total < 0:
        hugo = -1

total = 0
hugo = -1

for i in range(n):
    total += a[i]
    if hugo == -1 and total <= 0:
        ans_m = ans_m + (1-total)
        total = 1
        hugo = 1
    elif hugo == -1 and total > 0:
        hugo = 1
    elif hugo == 1 and total >= 0:
        ans_m = ans_m + (1+total)
        total = -1
        hugo = -1
    elif hugo == 1 and total < 0:
        hugo = -1

print(min(ans_m, ans_p))

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))

    def solve(positive, A):
        total = 0
        ope = 0
        for i in range(len(A)):
            # print("####")
            # print(total)
            # print(ope)
            if positive:
                # 次は負の数=正の数になるなら補正
                if total + A[i] >= 0:
                    ope += total + A[i] + 1
                    total = total + A[i] - (total + A[i]) - 1
                else:
                    total += A[i]
            else:
                # 次は正の数=負の数になるなら補正
                if total + A[i] <= 0:
                    ope += abs(total + A[i]) + 1
                    total = total + A[i] + abs(total + A[i]) + 1
                else:
                    total += A[i]
            positive = (not positive)
        return ope
    
    print(min(solve(True, A), solve(False, A)))



if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(_n) for _n in input().split()]
res0 = 0
s = 0
for i, a in enumerate(A):
    s += a
    if i % 2 == 0 and s >= 0:
        res0 += s + 1
        s = -1
    elif i % 2 == 1 and s <= 0:
        res0 += -s + 1
        s = 1
res1 = 0
s = 0
for i, a in enumerate(A):
    s += a
    if i % 2 == 1 and s >= 0:
        res1 += s + 1
        s = -1
    elif i % 2 == 0 and s <= 0:
        res1 += -s + 1
        s = 1
print(min(res0,res1))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

def solve(A, mode=0):
  # mode = 0 : +-+-+-...
  # mode = 1 : -+-+-+...
  res = 0
  pre_a = 0
  for i, a in enumerate(A):
    a += pre_a
    if a * (-1)**(i+mode) > 0: # 符号がmatchしている
      pre_a = a
      continue
    # 符号がmatchしていない
    res += abs(a) + 1
    pre_a = (-1) ** (i + mode)
  return res
  
ans = solve(A, mode=0)
ans = min(ans, solve(A, mode=1))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))

#      0  1  2  3  evn odd
# kevn +  -  +  -   +   -
# kodd -  +  -  +   -   +

def kf(a,flag,n):
    a0=a[0]*flag
    if a0<=0:
        kevn=1-a0
        sevn=1
    elif a0>0:
        kevn=0
        sevn=a0

    for i in range(1,n):
        ai=a[i]*flag
        if i%2==0:
            if sevn+ai<=0:
                kevn=kevn+1-(ai+sevn)
                sevn=1
            elif sevn+ai>0:
                kevn=kevn
                sevn=sevn+ai
        elif i%2==1:
            if sevn+ai<0:
                kevn=kevn
                sevn=sevn+ai
            elif sevn+ai>=0:
                kevn=kevn+1+(ai+sevn)
                sevn=-1
    return kevn

print(min(kf(a,1,n),kf(a,-1,n)))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))

#      0  1  2  3  evn odd
# kevn +  -  +  -   +   -
# kodd -  +  -  +   -   +

a0=a[0]
if a0<0:
    kevn=1-a0
    sevn=1
elif a0==0:
    kevn=1
    sevn=1
elif a0>0:
    kevn=0
    sevn=a0

for i in range(1,n):
    ai=a[i]
    if i%2==0:
        if sevn+ai<0:
            kevn=kevn+1-(ai+sevn)
            sevn=1
        elif sevn+ai==0:
            kevn=kevn+1
            sevn=1
        elif sevn+ai>0:
            kevn=kevn
            sevn=sevn+ai
    elif i%2==1:
        if sevn+ai<0:
            kevn=kevn
            sevn=sevn+ai
        elif sevn+ai==0:
            kevn=kevn+1
            sevn=-1
        elif sevn+ai>0:
            kevn=kevn+1+(ai+sevn)
            sevn=-1
kevn1=kevn
            
a0=-a[0]
if a0<0:
    kevn=1-a0
    sevn=1
elif a0==0:
    kevn=1
    sevn=1
elif a0>0:
    kevn=0
    sevn=a0

for i in range(1,n):
    ai=-a[i]
    if i%2==0:
        if sevn+ai<0:
            kevn=kevn+1-(ai+sevn)
            sevn=1
        elif sevn+ai==0:
            kevn=kevn+1
            sevn=1
        elif sevn+ai>0:
            kevn=kevn
            sevn=sevn+ai
    elif i%2==1:
        if sevn+ai<0:
            kevn=kevn
            sevn=sevn+ai
        elif sevn+ai==0:
            kevn=kevn+1
            sevn=-1
        elif sevn+ai>0:
            kevn=kevn+1+(ai+sevn)
            sevn=-1
            
kevn=min(kevn,kevn1)

print(kevn)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math

n = int(input())
a = list(map(int, stdin.readline().rstrip().split()))

#print(odd)
#print(pair)


## pair > odd
count_pair = 0
current_sum = 0
diff = 0
for i in range(len(a)):
    if i % 2 == 0:
        if current_sum + a[i] < 1:
            diff = 1 - (current_sum + a[i])
            count_pair += diff
        else:
            diff = 0
    elif i % 2 == 1:
        if current_sum + a[i] > -1:
            diff = -1 - (current_sum + a[i])
            count_pair += -1 * diff
        else:
            diff = 0

    current_sum += a[i] + diff
    if current_sum == 0:
        print("Error")

# odd > pair
count_odd = 0
current_sum = 0
diff = 0
i=0
for i in range(len(a)):
    if i % 2 == 1:
        if current_sum + a[i] < 1:
            diff = 1 - (current_sum + a[i])
            count_odd += diff
        else:
            diff = 0
    elif i % 2 == 0:
        if current_sum + a[i] > -1:
            diff = -1 - (current_sum + a[i])
            count_odd += -1 * diff
        else:
            diff = 0


    current_sum += a[i] + diff
    if current_sum == 0:
        print("Error")


print(min(count_odd, count_pair))