ABC-059-C Sequence

■■■問題■■■

長さNの数列があり、i番目の数はaiです。
あなたは1回の操作でどれか1つの項の値を1だけ増やすか減らすことができます。
以下の条件を満たすために必要な操作回数の最小値を求めてください。

●すべてのi(1 <= i <= n) に対し、第1項から第i項までの和は0でない
●すべてのi(1 <= i <= n-1) に対し、i項までの和と i+1 項までの和の符号が異なる

■■■入力■■■

n
a1 a2 ・・・ an

●2 <= n <= 10万
●|ai| <= 10億
●aiは整数

■■■出力■■■

必要な操作回数の最小値を出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4");
            WillReturn.Add("1 -3 1 0");
            //4
            //例えば、数列を1,-2,2,-2に4回の操作で変更することができます。
            //この数列は1,2,3,4項までの和がそれぞれ1,-1,1,-1であるため、
            //条件を満たしています。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("3 -6 4 -5 7");
            //0
            //はじめから条件を満たしています
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6");
            WillReturn.Add("-1 4 3 2 -5 4");
            //8
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        long Cost1 = Solve(AArr, true);
        long Cost2 = Solve(AArr, false);
        Console.WriteLine(Math.Min(Cost1, Cost2));
    }

    //配列と、プラス始まりかを引数として、コストを求める
    static long Solve(int[] pArr, bool pIsFirstPlus)
    {
        long Cost = 0;
        long RunSum = 0;

        for (int I = 0; I <= pArr.GetUpperBound(0); I++) {
            RunSum += pArr[I];
            if (I % 2 == 0 && pIsFirstPlus
             || I % 2 == 1 && pIsFirstPlus == false) {
                if (RunSum > 0) continue;
                Cost += Math.Abs(RunSum) + 1;
                RunSum = 1;
            }
            else {
                if (RunSum < 0) continue;
                Cost += Math.Abs(RunSum) + 1;
                RunSum = -1;
            }
        }
        return Cost;
    }
}

解説

マイナス始まりと、プラス始まりで
コストの低いほうが解となります。