ABC059

――――――――――――――――――――――――
問題文
長さ N の数列があり、i 番目の数は ai です。 あなたは 1回の操作でどれか 1 つの項の値を 1 だけ増やすか減らすことができます。
以下の条件を満たすために必要な操作回数の最小値を求めてください。
• すべてのi(1≦i≦n) に対し、第 1 項から第 i 項までの和は 0 でない
• すべてのi(1≦i≦n−1) に対し、i 項までの和と i+1 項までの和の符号が異なる
制約
• 2≦n≦10^5
• |ai|≦10^9
• ai は整数
________________________________________
入力
入力は以下の形式で標準入力から与えられる。
n
a1 a2 ...... an
出力
必要な操作回数の最小値を出力せよ。
――――――――――――――――――――――――

考え方

i項までの和とi+1項までの和が異なるので、パターンとして次の2通りが考えられる。
・奇数項までの和が正、偶数項までの和が負
・奇数項までの和が負、偶数項までの和が正
もし条件と異なる場合は、符号が変わるまで操作を行う。符号が変わるまでの操作回数は、和の絶対値+1となる。2つのパターンの操作回数をカウントしておき、少ないほうを出力する。

コード

using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

class Program{
 public static void Main(){
   
//入力
   int n = int.Parse(Console.ReadLine());
   var input = Console.ReadLine().Split();
   int[] a = new int[n];
   for(int i=0; i<n; i++){
     a[i] = int.Parse(input[i]);
   }
   
//和とカウント数を奇数項が正、偶数項が正でそれぞれ変数を用意
   long e_cnt = 0;
   long o_cnt = 0;
   long e_sum = 0;
   long o_sum = 0;

//1項目から足していって、操作を行う
   for(int i=0; i<n; i++){
     e_sum += a[i];
     o_sum += a[i];
     if(i % 2 == 1){
       if(e_sum >= 0){
         e_cnt += e_sum +1;
         e_sum = -1;
       }
       if(o_sum <= 0){
         o_cnt += Abs(o_sum) +1;
         o_sum = 1;
       }
     }
     else{
       if(e_sum <= 0){
         e_cnt += Abs(e_sum) +1;
         e_sum = 1;
       }
       if(o_sum >= 0){
         o_cnt += o_sum +1;
         o_sum = -1;
       }
     }
   }

//操作回数が少ないほうを出力
   Console.Write(Min(o_cnt,e_cnt));
 }
}

和の条件2パターンと、項数が奇数か偶数かで場合分けをしたため、4パターンに分けている。ちょっと煩雑な感じになっててもっと効率のいい方法ないかなーと思ったけど、他の人もだいたいこんな感じだった。

これくらいの時期の問題だと、C問題は文法がわかれば解ける感じだなー。
もうちょっと手ごたえ欲しいけど、D問題だとかなり時間かかっちゃいそうだし悩むなー。

note、Shift + Enterで段落の中で改行できることを知った…！