145AC - ABC059C: Sequence - back-of-the-envelope

ABC059-C (300 points)

問題

長さ $n$ の数列 $(a_1, a_2, \ldots, a_n)$ に対して, どれか $1$ つの項の値を $1$ 増やす（減らす）という操作を行い, 以下の条件を満たす数列にするために必要な操作の最小回数を求める.

すべての $i (1 \leq i \leq n)$ に対し, 第 $1$ 項から第 $i$ 項までの和 $0$ でない
すべての $i (1 \leq i \leq n - 1)$ に対し, 第 $i$ 項までの和と第 $i + 1$ 項までの和の符号が異なる

$2 \leq n \leq 10^5$
$|a_i| \leq 10^9$
入力は全て整数

方針

偶数番目の項までの和を正にする場合と, 奇数番目の項までの和を正にする場合をそれぞれ考え, 回数の少ない方を出力.
第 $1$ 項から順番に見ていき, 条件を満たさない場合は条件をギリギリ満たす（和が $1$ or $-1$ ）になるようにする.

# input
n = int(input())
A = list(map(int, input().split()))

# 偶数番目が＋
A_even = A[:]
S_even = 0
ans_even = 0
for i in range(n):
    if (S_even + A_even[i]) * ((-1) ** (i - 1)) > 0:
        S_even += A_even[i]
        continue
    A_even[i] = (-1) ** (i - 1) - S_even
    ans_even += abs(A[i] - A_even[i])
    S_even = (-1) ** (i - 1)

# 奇数番目が＋
A_odd = A[:]
S_odd = 0
ans_odd = 0
for i in range(n):
    if (S_odd + A_odd[i]) * ((-1) ** i) > 0:
        S_odd += A_odd[i]
        continue
    A_odd[i] = (-1) ** i - S_odd
    ans_odd += abs(A[i] - A_odd[i])
    S_odd = (-1) ** i

ans = int(min(ans_even, ans_odd))