67470


# 問題文

> 長さ 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`を左から順に１つづつ増やして答えを検証する。

以下２つの条件であれば、何もしない。

  * `previous_sum`がプラスかつ、`A[i]`のマイナス値が`previous_sum`よりも小さい
  * `previous_sum`がマイナスかつ、`A[i]`のプラス値が`previous_sum`よりも大きい

以下２つの条件

  * `previous_sum`がプラスかつ、`A[i]`のマイナス値が`previous_sum`以上
  * `previous_sum`がマイナスかつ、`A[i]`のプラス値が`previous_sum`以下

ならば、`previous_sum`と`A[i]`の合計が１あるいは-1となるようにして  
与えられた条件を満たすようにする。

> ・すべてのi(1≦i≦n−1) に対し、i 項までの和と i+1 項までの和の符号が異なる

## 提出したソースコード

[code]

    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)
    
[/code]


CC BY-SA 4.0
2020-06-09T14:46:12.297
67468
2020-06-09T16:54:44.690
9616
question
python python3
AtCoder Beginner Contest 059 C問題で不正解が発生する


初項を変更することが検討されていません。

[code]

    2
    1 1000
    
[/code]

これは初項を-1に変えればいいので、答えは2です。

[code]

    2
    0 0
    
[/code]

これは1 -2などに変える必要があるので、答えは3です。


CC BY-SA 4.0
2020-06-09T16:54:44.690
67470
2020-06-09T16:54:44.690
33033
67468
answer