Sequence [AtCoder Beginner Contest 059 C]

atcoder.jp

与えられた数列の項を操作して累積和を [正,負,正,負......] もしくは [負,正,負,正......] の形にするとき、操作回数の最小値を求めよ。ただし、累積和は一度でも0であってはならない、という問題です。

偶数項を正とするのか、奇数項を正とするのかについては、例のごとくどちらも試してみて、それから最小値を求めればよいです。

操作回数については、順番に累積和を求めながら計算していきます。もし偶数項を正とするとき、ある偶数項までの累積和 X が正なら操作回数は0、負ならその時点の累積和を1まで引き上げればよいので、Math.abs(X)+1 を操作回数に加算し、その時点の累積和を Math.abs(X)+1 とします。負の場合、また、奇数項を正とする場合も同様です。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		int n = sc.nextInt();
		int[] ar = new int[n];
		for (int i=0; i<n; i++) ar[i] = sc.nextInt();
		
		//偶数項を正としたときの操作回数minA
		long minA = 0;
		long sumA = 0;
		for (int i=0; i<n; i++) {
			sumA += ar[i];
			if (i%2 == 0) {
				if (sumA <= 0) {
					minA += Math.abs(sumA) + 1;
					sumA += Math.abs(sumA) + 1;
				}
			}
			else { //sumA -
				if (sumA >= 0) {
					minA += Math.abs(sumA) + 1;
					sumA -= Math.abs(sumA) + 1;
				}
			}
		}
		
		//奇数項を正としたときの操作回数minB
		long minB = 0;
		long sumB = 0;
		for (int i=0; i<n; i++) {
			sumB += ar[i];
			if (i%2 != 0) {
				if (sumB <= 0) {
					minB += Math.abs(sumB) + 1;
					sumB += Math.abs(sumB) + 1;
				}
			}
			else {
				if (sumB >= 0) {
					minB += Math.abs(sumB) + 1;
					sumB -= Math.abs(sumB) + 1;
				}
			}
		}
		
		System.out.println(Math.min(minA, minB));
		
	}
}

実装に少し手間取ってしまいました。数学的な実装……といってもただの足し算引き算なのですが、比較演算子に = を付けていなかったりと、細かいところまで意識が行き届いていませんね。