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:
import copy


def resolve(L_input):
    L = copy.deepcopy(L_input)
    cnt = 0
    s = L[0]
    for i in range(1, len(L)):
        a = L[i]
        if s > 0 and s+a >= 0:
            L[i] = -s-1
            cnt += (s+a+1)
            s = -1
        elif s < 0 and s+a <= 0:
            L[i] = -s+1
            cnt += (-s-a+1)
            s = 1
        else:
            s += a

    return cnt


def solution(L):
    first_term = L[0]
    if first_term > 0:
        L_positive = L
        first_positibe_cnt = resolve(L_positive)
        # extract first_term+1 to first_term to be -1
        L_negative = [-1]+L[1:]
        first_negative_cnt = (first_term+1) + resolve(L_negative)
    elif first_term < 0:
        # add -first_term+1 to first_term to be 1
        L_positive = [1]+L[1:]
        first_positibe_cnt = (-first_term+1) + resolve(L_positive)
        L_negative = L
        first_negative_cnt = resolve(L_negative)
    else:
        # add 1 to first_term to be 1
        L_positive = [1]+L[1:]
        first_positibe_cnt = 1 + resolve(L_positive)
        # extract 1 to first_term to be -1
        L_negative = [-1]+L[1:]
        first_negative_cnt = 1 + resolve(L_negative)

    # print("first_positive, cnt: {}".format(first_positibe_cnt))
    # print(L_positive)
    # print("first_negative_cnt, cnt: {}".format(first_negative_cnt))
    # print(L_negative)

    return min(first_positibe_cnt, first_negative_cnt)


if __name__ == "__main__":
    N = int(input())
    L = list(map(int, input().split(' ')))
    print(solution(L))

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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

    N = ii()
    A = il()

    # 偶数番目の合計を負
    # 奇数番目の合計を正にするパターン
    sm, r1 = 0, 0
    for n in range(N):
        sm += A[n]
        if n % 2 == 0 and sm < 1:
            r1 += abs(sm) + 1
            sm = 1
        elif n % 2 != 0 and sm > -1:
            r1 += abs(sm) + 1
            sm = -1

    # 偶数番目の合計を正
    # 奇数番目の合計を負にするパターン
    sm, r2 = 0, 0
    for n in range(N):
        sm += A[n]
        if n % 2 == 0 and sm > -1:
            r2 += abs(sm) + 1
            sm = -1
        elif n % 2 != 0 and sm < 1:
            r2 += abs(sm) + 1
            sm = 1

    # 操作数が小さいほうを出力
    print(min(r1, r2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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

    N = ii()
    A = il()

    sm, r1 = 0, 0
    for n in range(N):
        sm += A[n]
        if n % 2 == 0 and sm < 1:
            r1 += abs(sm) + 1
            sm = 1
        elif n % 2 != 0 and sm > -1:
            r1 += abs(sm) + 1
            sm = -1

    sm, r2 = 0, 0
    for n in range(N):
        sm += A[n]
        if n % 2 == 0 and sm > -1:
            r2 += abs(sm) + 1
            sm = -1
        elif n % 2 != 0 and sm < 1:
            r2 += abs(sm) + 1
            sm = 1

    print(min(r1, r2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())

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

memo_1 = [0]*n
memo_1_ruiseki = [0]*n
memo_2 = [0]*n
memo_2_ruiseki = [0]*n

for i in range(n):
    if i%2==0:
        if memo_1_ruiseki[i-1]+a[i] < 0:
            memo_1[i] = abs(memo_1_ruiseki[i-1])+1
        elif memo_1_ruiseki[i-1]+a[i] == 0:
            memo_1[i] = a[i]+1
        else:
            memo_1[i] = a[i]
    else:
        if memo_1_ruiseki[i-1]+a[i] > 0:
            memo_1[i] = -1+(-1)*abs(memo_1_ruiseki[i-1])
        elif memo_1_ruiseki[i-1]+a[i] == 0:
            memo_1[i] = -1+a[i]
        else:
            memo_1[i] = a[i]
    memo_1_ruiseki[i] = memo_1_ruiseki[i-1]+memo_1[i]

for i in range(n):
    if i%2==1:
        if memo_2_ruiseki[i-1]+a[i] < 0:
            memo_2[i] = abs(memo_2_ruiseki[i-1])+1
        elif memo_2_ruiseki[i-1]+a[i] == 0:
            memo_2[i] = a[i]+1
        else:
            memo_2[i] = a[i]
    else:
        if memo_2_ruiseki[i-1]+a[i] > 0:
            memo_2[i] = -1+(-1)*abs(memo_2_ruiseki[i-1])
        elif memo_2_ruiseki[i-1]+a[i] == 0:
            memo_2[i] = -1+a[i]
        else:
            memo_2[i] = a[i]
    memo_2_ruiseki[i] = memo_2_ruiseki[i-1]+memo_2[i]

ans_1 = 0
ans_2 = 0

for i in range(n):
    ans_1 += abs(memo_1[i]-a[i])
    ans_2 += abs(memo_2[i]-a[i])

print(min(ans_1,ans_2))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=10**18
for i in range(2):
    accum=0
    cnt=0
    if i:
        for i in range(n):
            if i%2:
                if accum+a[i]>=0:
                    cnt+=(accum+a[i])+1
                    accum=-1
                else:
                    accum+=a[i]
            else:
                if accum+a[i]<=0:
                    cnt+=1-(accum+a[i])
                    accum=1
                else:
                  accum+=a[i]
        ans=min(ans,cnt)
    else:
        for i in range(n):
            if i%2==0:
                if accum+a[i]>=0:
                    cnt+=(accum+a[i])+1
                    accum=-1
                else:
                    accum+=a[i]
            else:
                if accum+a[i]<=0:
                    cnt+=1-(accum+a[i])
                    accum=1
                else:
                    accum+=a[i]
        ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
A = getList()
num = copy.deepcopy(A)

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

# + - + -
margin_1 = 0
num_1 = copy.deepcopy(num)
cnt_1 = 0
for i in range(N):
    num_1[i] += margin_1
    if i % 2 == 0:
        plus = max(1 - num_1[i], 0)
        num_1[i] += plus
        margin_1 += plus
        cnt_1 += plus
    else:
        minus = max(num_1[i] - (-1), 0)
        num_1[i] -= minus
        margin_1 -= minus
        cnt_1 += minus

margin_2 = 0
num_2 = copy.deepcopy(num)
cnt_2 = 0
for i in range(N):
    num_2[i] += margin_2
    if i % 2 != 0:
        plus = max(1 - num_2[i], 0)
        num_2[i] += plus
        margin_2 += plus
        cnt_2 += plus
    else:
        minus = max(num_2[i] - (-1), 0)
        num_2[i] -= minus
        margin_2 -= minus
        cnt_2 += minus

print(min(cnt_1, cnt_2))

Submission status: Accepted

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

#i%2==0 の時+
cnt=0
sums=0

for i in range(n):
    if i%2==0:
        if sums+a[i]<=0:
            tmp=abs(sums+a[i])+1
            sums=1
            cnt+=tmp
        else:
            sums+=a[i]
            tmp=a[i]
    else:
        #マイナスになってほしい
        if sums+a[i]>=0:
            tmp=abs(sums+a[i])+1
            sums=-1
            cnt+=tmp
        else:
            sums+=a[i]
            tmp=a[i]
    #print(a[i],tmp)

ans=cnt
#print("##############")
#i%2==0 の時+
cnt=0
sums=0

for i in range(n):
    if i%2==1:
        if sums+a[i]<=0:
            tmp=abs(sums+a[i])+1
            sums=1
            cnt+=tmp
        else:
            tmp=a[i]
            sums+=a[i]
    else:
        #マイナスになってほしい
        if sums+a[i]>=0:
            tmp=abs(sums+a[i])+1
            sums=-1
            cnt+=tmp
        else:
            tmp=a[i]
            sums+=a[i]
    #print(a[i],tmp)

print(min(cnt,ans))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))

    ans1 = 0
    total = 0
    is_plus = True
    for a in A:
        total += a

        if is_plus:
            if total <= 0:
                ans1 += -total + 1
                total = 1
        else:
            if total >= 0:
                ans1 += total + 1
                total = -1

        is_plus = not is_plus

    ans2 = 0
    total = 0
    is_plus = False
    for a in A:
        total += a

        if is_plus:
            if total <= 0:
                ans2 += -total + 1
                total = 1
        else:
            if total >= 0:
                ans2 += total + 1
                total = -1

        is_plus = not is_plus

    print(min(ans1, ans2))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = list(map(int, readline().split()))
    b = [0] * n
    c = [0] * n

    score1 = 0
    cur = 0
    for i, x in enumerate(a):
        if i % 2 == 0:
            nx = x + cur
            if nx <= 0:
                diff = abs(nx) + 1
                score1 += diff
                cur = 1
            else:
                cur = nx
        else:
            nx = x + cur
            if nx >= 0:
                diff = abs(nx) + 1
                score1 += diff
                cur = -1
            else:
                cur = nx

    score2 = 0
    cur = 0
    for i, x in enumerate(a):
        if i % 2 == 1:
            nx = x + cur
            if nx <= 0:
                diff = abs(nx) + 1
                score2 += diff
                cur = 1
            else:
                cur = nx
        else:
            nx = x + cur
            if nx >= 0:
                diff = abs(nx) + 1
                score2 += diff
                cur = -1
            else:
                cur = nx

    print(min(score1, score2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def first_positive(n,a):
    count = 0
    sum = a[0]
    #正ならTrue
    flag = True

    if a[0] <= 0:
        sum = 1
        count += abs(1 - a[0])

    for i in range(1,n):
        if sum + a[i] < 0 and flag == True:
            sum += a[i]
            flag = False
            continue
        elif sum + a[i] <= 0 and flag == False:
            flag = True
            count += abs(1 - sum - a[i])
            sum = 1
        elif sum + a[i] >= 0 and flag == True:
            flag = False
            count += abs(-1 - sum - a[i])
            sum = -1
        elif sum + a[i] > 0 and flag == False:
            sum += a[i]
            flag = True
            continue

    return count

def first_negative(n,a):
    count = 0
    sum = a[0]
    #正ならTrue
    flag = False

    if a[0] >= 0:
        sum = -1
        count += abs(-1 - a[0])

    for i in range(1,n):
        if sum + a[i] < 0 and flag == True:
            sum += a[i]
            flag = False
            continue
        elif sum + a[i] <= 0 and flag == False:
            flag = True
            count += abs(1 - sum - a[i])
            sum = 1
        elif sum + a[i] >= 0 and flag == True:
            flag = False
            count += abs(-1 - sum - a[i])
            sum = -1
        elif sum + a[i] > 0 and flag == False:
            sum += a[i]
            flag = True
            continue

    return count

if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]

    p = first_positive(n,a)
    n = first_negative(n,a)

    if p < n:
        print(p)
    else:
        print(n)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]

count1 = 0
count2 = 0
sum = 0

for i in range(0,n):
    if i % 2 == 0:
        if sum + a[i] > 0:
            sum += a[i]
            continue
        elif sum + a[i] <= 0:
            count1 += abs(1 - sum -a[i])
            sum = 1
    elif i % 2 == 1:
        if sum + a[i] < 0:
            sum += a[i]
            continue
        else:
            count1 += abs(-1 - sum - a[i])
            sum = -1

sum = 0
for i in range(0,n):
    if i % 2 == 1:
        if sum + a[i] > 0:
            sum += a[i]
            continue
        elif sum + a[i] <= 0:
            count2 += abs(1 - sum -a[i])
            sum = 1
    elif i % 2 == 0:
        if sum + a[i] < 0:
            sum += a[i]
            continue
        else:
            count2 += abs(-1 - sum - a[i])
            sum = -1

if count1 >= count2:
    print(count2)
else:
    print(count1)

Submission status: Accepted

Solution code:
import unittest


def solve(n, a):
    # 貪欲
    cnt = 0
    total = a[0]
    if a[0] < 1:
        cnt = abs(a[0]) + 1
        total = 1
    for i in range(1, n):
        if i % 2 == 0:  # +
            if total + a[i] > 0:
                total += a[i]
            else:
                diff = abs(total + a[i]) + 1
                cnt += abs(diff)
                total = 1
        else:  # -
            if total + a[i] < 0:
                total += a[i]
            else:
                diff = abs(total + a[i]) + 1
                cnt += abs(diff)
                total = -1
    t = cnt
    cnt = 0
    total = a[0]
    if a[0] > -1:
        cnt = abs(a[0]) + 1
        total = -1
    for i in range(1, n):
        if i % 2 == 0:  # -
            if total + a[i] < 0:
                total += a[i]
            else:
                diff = abs(total + a[i]) + 1
                cnt += abs(diff)
                total = -1
        else:  # +
            if total + a[i] > 0:
                total += a[i]
            else:
                diff = abs(total + a[i]) + 1
                cnt += abs(diff)
                total = 1

    return min(t, cnt)


def main():
    n = int(input())
    a = list(map(int, input().split()))
    result = solve(n, a)
    print(result)


if __name__ == "__main__":
    main()


class Test(unittest.TestCase):
    def test_solve_1(self):
        n = 4
        a = [1, -3, 1, 0]
        actual = solve(n, a)
        expected = 4
        self.assertEqual(actual, expected)

    def test_solve_2(self):
        n = 5
        a = [3, -6, 4, -5, 7]
        actual = solve(n, a)
        expected = 0
        self.assertEqual(actual, expected)

    def test_solve_3(self):
        n = 6
        a = [-1, 4, 3, 2, - 5, 4]
        actual = solve(n, a)
        expected = 8
        self.assertEqual(actual, expected)

    def test_solve_4(self):
        n = 6
        a = [-1, 2, -2, 2, -2, 1000]
        actual = solve(n, a)
        expected = 0
        self.assertEqual(actual, expected)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]


# plusスタートにする
ans1 = 0
c = 0
plus = True
for a in A:
    c += a
    if plus:
        if c <= 0:
            ans1 += abs(c) + 1
            c = 1
        plus = False
    else:
        if c >= 0:
            ans1 += abs(c) + 1
            c = -1
        plus = True

# minusスタートにする
ans2 = 0
c = 0
plus = False
for a in A:
    c += a
    if plus:
        if c <= 0:
            ans2 += abs(c) + 1
            c = 1
        plus = False
    else:
        if c >= 0:
            ans2 += abs(c) + 1
            c = -1
        plus = True

print(min(ans1, ans2))

Submission status: Accepted

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

ans1 = 0
s = 0
for i,a in enumerate(A):
    s += a
    if i%2:
        if s > -1:
            ans1 += s+1
            s = -1
    else:
        if s < 1:
            ans1 += 1-s
            s = 1

ans2 = 0
s = 0
for i,a in enumerate(A):
    s += a
    if i%2==0:
        if s > -1:
            ans2 += s+1
            s = -1
    else:
        if s < 1:
            ans2 += 1-s
            s = 1

print(min(ans1, ans2))

Submission status: Accepted

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

# minus
imos = 0
minusans = 0
for i in range(n):
	targ = ruisekiwa[i] + imos
	if i % 2 == 0:
		if targ >= 0:
			imos -= targ+1
			minusans += targ+1
	else:
		if targ <= 0:
			imos += 1-targ
			minusans += 1-targ

# plus
imos = 0
plusans = 0
for i in range(n):
	targ = ruisekiwa[i] + imos
	if i % 2 == 1:
		if targ >= 0:
			imos -= targ+1
			plusans += targ+1
	else:
		if targ <= 0:
			imos += 1-targ
			plusans += 1-targ

print(min(minusans, plusans))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans_o=0
cnt_o=0
ans_e=0
cnt_e=0
for i in range(n):
  cnt_o+=a[i]
  if i%2==0:
    if cnt_o>0:
      continue
    else:
      ans_o+=abs(cnt_o)+1
      cnt_o=1
  else:
    if cnt_o<0:
      continue
    else:
      ans_o+=cnt_o+1
      cnt_o=-1
for i in range(n):
  cnt_e+=a[i]
  if i%2==0:
    if cnt_e<0:
      continue
    else:
      ans_e+=cnt_e+1
      cnt_e=-1
  else:
    if cnt_e>0:
      continue
    else:
      ans_e+=abs(cnt_e)+1
      cnt_e=1
print(min(ans_o,ans_e))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
cnt_1=0
cnt_2=0
sum_1=0
sum_2=0

for i in range(N):
    sum_1+=A[i]
    if i%2==1:
        if sum_1<=0:
            cnt_1+=1-sum_1
            sum_1=1
    else:
        if sum_1>=0:
            cnt_1+=sum_1+1
            sum_1=-1

for i in range(N):
    sum_2+=A[i]
    if i%2==1:
        if sum_2>=0:
            cnt_2+=sum_2+1
            sum_2=-1
    else:
        if sum_2<=0:
            cnt_2+=1-sum_2
            sum_2=1

print(min(cnt_1,cnt_2))

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7


# segment tree

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x, y: x + y, default=0):
        self.size = 2 ** (size - 1).bit_length()  # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default] * (self.size * 2)  # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)  # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


n = ir()
a = lr()
seg1 = SegmentTree(n, lambda x, y: x + y, 0)
seg2 = SegmentTree(n, lambda x, y: x + y, 0)
for i, num in enumerate(a):
    seg1.update(i, num)  # 0オリジンのi個目をnumに更新 O(n)
    seg2.update(i, num)  # 0オリジンのi個目をnumに更新 O(n)
ans1 = 0
ans2 = 0
pflag = True
pflag2 = False
for i in range(1,n+1):
    now1 = seg1.query(0,i)
    if pflag and now1 <= 0:
        seg1.update(i-1, a[i-1]-now1+1)
        ans1+=(1-now1)
    elif (not pflag) and now1 >= 0:
        seg1.update(i-1, a[i-1]-now1-1)
        ans1+=(now1+1)
    now2 = seg2.query(0,i)
    if pflag2 and now2 <= 0:
        seg2.update(i-1, a[i-1]-now2+1)
        ans2+=(1-now2)
    elif (not pflag2) and now2 >= 0:
        seg2.update(i-1, a[i-1]-now2-1)
        ans2+=(now2+1)
    pflag = not pflag
    pflag2 = not pflag2
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
L = [0 for _ in range(n)]
L[0] = a[0]
for i in range(1, n):
  L[i] = L[i-1] + a[i]
delay = 0
all_over = 0
anti_delay = 0
anti_all_over = 0
if a[0] != 0:
  antiL = L[:]
  sign = (a[0] > 0) - (a[0] < 0)
  for i in range(1, n):
    L[i] += delay
    if L[i] <= 0 and sign == -1:
      delay += 1 - L[i]
      all_over += 1 - L[i]
      L[i] = 1
    elif L[i] >= 0 and sign == 1:
      delay -= L[i] + 1
      all_over += L[i] + 1
      L[i] = -1
    sign *= -1
  if antiL[0] < 0:
    sign = 1
    anti_delay = 1 - antiL[0]
    anti_all_over = 1 - antiL[0]
  else:
    sign = -1
    anti_delay = -(antiL[0] + 1)
    anti_all_over = antiL[0] + 1
  for i in range(1, n):
    antiL[i] += anti_delay
    if antiL[i] <= 0 and sign == -1:
      anti_delay += 1 - antiL[i]
      anti_all_over += 1 - antiL[i]
      antiL[i] = 1
    elif antiL[i] >= 0 and sign == 1:
      anti_delay -= antiL[i] + 1
      anti_all_over += antiL[i] + 1
      antiL[i] = -1
    sign *= -1
  print(min(anti_all_over, all_over))
else:
  posL = L[:]
  negL = L[:]
  pos_delay, neg_delay = 1, -1
  pos_all_over, neg_all_over = 1, 1
  sign = 1
  for i in range(1, n):
    posL[i] += pos_delay
    if posL[i] <= 0 and sign == -1:
      pos_delay += 1 - posL[i]
      pos_all_over += 1 - posL[i]
      posL[i] = 1
    elif posL[i] >= 0 and sign == 1:
      pos_delay -= posL[i] + 1
      pos_all_over += posL[i] + 1
      posL[i] = -1
    sign *= -1
  sign = -1
  for i in range(1, n):
    negL[i] += neg_delay
    if negL[i] <= 0 and sign == -1:
      neg_delay += 1 - negL[i]
      neg_all_over += 1 - negL[i]
      negL[i] = 1
    elif negL[i] >= 0 and sign == 1:
      neg_delay -= negL[i] + 1
      neg_all_over += negL[i] + 1
      negL[i] = -1
    sign *= -1
  print(min(pos_all_over, neg_all_over))

Submission status: Accepted

Solution code:
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

    n = int(input())
    A = list(map(int, input().split()))
    val=0
    ans = 0
    for i in range(len(A)):
        val+=A[i]
        if val>=0 and i%2==0:
            ans+=val+1
            val=-1
        elif val<=0 and i%2==1:
            ans+=abs(val)+1
            val=1
    val=0
    ans2=0
    for i in range(len(A)):
        val+=A[i]
        if val>=0 and i%2==1:
            ans2+=val+1
            val=-1
        elif val<=0 and i%2==0:
            ans2+=abs(val)+1
            val=1


    print(min(ans2,ans))



resolve()

Submission status: Accepted

Solution code:
n = int(input())
alst = list(map(int, input().split()))
ans = []
for pm in range(2):
    total = 0
    tmp = 0
    for j, num in enumerate(alst):
        total += num
        if (j + pm) % 2 == 0:
            if total > 0:
                pass
            else:
                tmp += abs(1 - total)
                total = 1
        else:
            if total < 0:
                pass
            else:
                tmp += abs(-1 - total)
                total = -1
    ans.append(tmp)
print(min(ans))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
ans = 10**15

for i in [-1,1]:
    ansi,sum=0,0
    for a in A:
        sum+=a
        if sum*i<=0:
          ansi+=abs(sum-i)
          sum=i
        i*=-1
    ans=min(ans,ansi)
print(ans)

Submission status: Accepted

Solution code:
n=input()
a=[int(i) for i in input().split()]
def chk(a,t):
    ans=0
    x=0
    for i in a:
        x+=i
        if t==True and x<1:
            ans+=1-x
            x=1
        elif t==False and x>-1:
            ans+=x+1
            x=-1
        t=not t
    return ans
print(min(chk(a,True),chk(a,False)))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
tmp=0
csum_a=[]
for ai in a:
  tmp+=ai
  csum_a.append(tmp)
ans=0
tmp=0
plus=True
for si in csum_a:
  if plus and si+tmp>0:
    pass
  elif plus and si+tmp<=0:
    ans+=1-(si+tmp)
    tmp+=1-(si+tmp)
  elif not plus and si+tmp<0:
    pass
  elif not plus and si+tmp>=0:
    ans+=1+(si+tmp)
    tmp-=1+si+tmp
  plus=not plus

ans0=ans
ans=0
tmp=0
plus=False
for si in csum_a:
  if plus and si+tmp>0:
    pass
  elif plus and si+tmp<=0:
    ans+=1-(si+tmp)
    tmp+=1-(si+tmp)
  elif not plus and si+tmp<0:
    pass
  elif not plus and si+tmp>=0:
    ans+=1+(si+tmp)
    tmp-=1+si+tmp
  plus=not plus

print(min(ans0,ans))

Submission status: Accepted

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

def simulate_operation(tgt_list):
  answer = 0
  N = len(tgt_list)
  previous_sum = tgt_list[0] # total to i - 1
  for i in range(1, N):
    # if prev_sum is plus and tgt_lis[i] is more minus than prev_sum, no action.
    # if prev_sum is plus and minus of tgt_lis[i] is larger than or equal to prev_sum.
    if previous_sum > 0 and previous_sum + tgt_list[i] >= 0:
      # the number that need to be subtracted to meet the requirements.
      require_subtraction = previous_sum + tgt_list[i] + 1
      # correcting the current number.
      tgt_list[i] -= require_subtraction
      answer += require_subtraction
    # if prev_sum is minus and tgt_lis[i] is more plus than prev_sum, no action.
    # if prev_sum is minus and minus of tgt_lis[i] is more smaller than or equal to prev_sum.
    elif previous_sum < 0 and previous_sum + tgt_list[i] <= 0:
      # the number that need to be added to meet the requirements.
      require_addition = -(previous_sum + tgt_list[i] - 1)
      # correcting the current number.
      tgt_list[i] += require_addition
      answer += require_addition
    previous_sum += tgt_list[i]
  return answer

ans_list = []
# simulate two options of starting with a positive or negative.
# positive, the first item is 1.
ans_pos = 0
A_pos = A[:]
init_cost = A_pos[0] - 1
ans_pos += abs(init_cost)
A_pos[0] -= init_cost
ans_pos += simulate_operation(A_pos)
ans_list.append(ans_pos)
# negative, the first item is -1.
ans_neg = 0
A_neg = A[:]
init_cost = A_neg[0] + 1
ans_neg += abs(init_cost)
A_neg[0] -= init_cost
ans_neg += simulate_operation(A_neg)
ans_list.append(ans_neg)
# simulate straight
ans_straight = 0
if A[0] != 0:
  ans_straight = simulate_operation(A)
  ans_list.append(ans_straight)

print(min(ans_list))

Submission status: Accepted

Solution code:
#damedatta..
def main():
    n = int(input())
    a = list(map(int, input().split()))
    ms = 0
    ps = 0
    mr = 0
    pr = 0
    for i, v in enumerate(a):
        if i % 2:
            if ms + v < 0:
                ms += v
            else:
                mr += abs(-1 - ms - v)
                ms = -1
            if ps + v > 0:
                ps += v
            else:
                pr += abs(1-ps-v)
                ps = 1
        else:
            if ms + v > 0:
                ms += v
            else:
                mr += abs(1-ms-v)
                ms = 1
            if ps + v < 0:
                ps += v
            else:
                pr += abs(-1-ps-v)
                ps = -1
    return min(mr, pr)
print(main())