AtCoder ARC #129 : D - -1+2-1

この回はいまいちだった。
https://atcoder.jp/contests/arc129/tasks/arc129_d

問題

N要素の整数列Aが与えられる。
iを指定してA[i]に2を足し、A[i-1]とA[i]から1を引く、ということを繰り返してAの全要素を0にできるか。
(ただし、A[-1]はA[N-1]、A[N]はA[0]を表すとする)
できるなら最小処理回数を求めよ。

解法

iの指定回数をB[i]とすると、2*B[i]-B[i-1]-B[i+1]=-A[i]となる。
C[i]=B[i+1]-B[i]とすると、C[i]-C[i-1]=A[i]と置くことができる。
よってC[0]を定めれば、連鎖的にCが確定する。ここで、sum(C)=0なのでここからC[0]も確定できる。

Cが確定したら、Bの最小値が0になるようにBを定めていこう。

int N;
int A[202020];
ll B[202020];
ll C[202020];
void solve() {
	int i,j,k,l,r,x,y;;
	
	cin>>N;
	
	ll s=0;
	FOR(i,N) {
		cin>>A[i];
		s+=A[i];
	}
	if(s) {
		cout<<-1<<endl;
		return;
	}
	s=0;
	for(i=1;i<N;i++) {
		B[i]=B[i-1]+A[i];
		s+=B[i];
	}
	if(s%N) {
		cout<<-1<<endl;
		return;
	}
	ll mi=0;
	for(i=1;i<N;i++) {
		B[i]-=s/N;
		C[i]=C[i-1]+B[i];
		mi=min(mi,C[i]);
	}
	ll ret=0;
	FOR(i,N) {
		C[i]-=mi;
		ret+=C[i];
	}
	
	cout<<ret<<endl;
}

まとめ

差を取ったり累積和を取ったり、本番近いところまで行ったのに詰め切れなかった…。