問題文
長さ N の数列があり、i 番目の数は ai です。
あなたは 1 回の操作でどれか 1 つの項の値を 1だけ増やすか減らすことができます。
以下の条件を満たすために必要な操作回数の最小値を求めてください。
・すべてのi(1≦i≦n) に対し、第 1 項から第 i 項までの和は 0 でない
・すべてのi(1≦i≦n−1) に対し、i 項までの和と i+1 項までの和の符号が異なる
https://atcoder.jp/contests/abc059/tasks/arc072_a
疑問
テストケースでは全て成功するのですが、
ジャッジに通すと半分以上不正解が出てしまいます。
自身のソースの何が間違っているのかを明らかにしたいです。
回答方針
与えられる長さNの数列をA
と表す。
0番からi-1番目までの数列の合計をprevious_sum
とする。
数列A
のprevious_sum
を左から順に1つづつ増やして答えを検証する。
以下2つの条件であれば、何もしない。
previous_sum
がプラスかつ、A[i]
のマイナス値がprevious_sum
よりも小さいprevious_sum
がマイナスかつ、A[i]
のプラス値がprevious_sum
よりも大きい
以下2つの条件
previous_sum
がプラスかつ、A[i]
のマイナス値がprevious_sum
以上previous_sum
がマイナスかつ、A[i]
のプラス値がprevious_sum
以下
ならば、previous_sum
とA[i]
の合計が1あるいは-1となるようにして
与えられた条件を満たすようにする。
・すべてのi(1≦i≦n−1) に対し、i 項までの和と i+1 項までの和の符号が異なる
提出したソースコード
N = int(input())
A = list(map(int, input().split()))
ans = 0
previous_sum = A[0] # total to i - 1
for i in range(1, N):
# もしprevious_sumがプラスかつ、A[i]のマイナス値がprevious_sumよりも小さければ何もしない。
# もしprevious_sumがプラスかつ、A[i]のマイナス値がprevious_sum以上であれば↓
if previous_sum > 0 and previous_sum + A[i] >= 0:
# 条件を満たすために減算する必要のある数
require_subtraction = previous_sum + A[i] + 1
A[i] -= require_subtraction
ans += require_subtraction
# もしprevious_sumがマイナスかつ、A[i]のプラス値がprevious_sumよりも大きれば何もしない。
# もしprevious_sumがマイナスかつ、A[i]のプラス値がprevious_sum以下であれば↓
elif previous_sum < 0 and previous_sum + A[i] <= 0:
# 条件を満たすために加算する必要のある数
require_addition = -(previous_sum + A[i] - 1)
A[i] += require_addition
ans += require_addition
previous_sum += A[i]
print(ans)