Codeforces #843 : Div2 E. The Human Equation

フル参加できなかった回。
https://codeforces.com/contest/1775/problem/E

問題

整数列Aが与えられる。
ここに以下の処理を繰り返す。
Aのindexの部分列を取り出す。
奇数番目と偶数番目に登場するindexに対応するAの要素に対し、それぞれ+1/-1するか-1/+1することができる。
全体を0にするのに最小何回処理を行う必要があるか。

解法

Aを先頭から見て行ったとき、あるところでX回+1を行った場合、のちにX回ノーコストで-1できる。
±逆の場合も同様。

よってノーコストで+1/-1できる回数を数えながら、先頭から0にしていこう。

int T,N;
ll A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll X=0,Y=0;
		FOR(i,N) {
			cin>>A[i];
			if(A[i]>0) {
				X-=min(X,A[i]);
				Y+=A[i];
			}
			if(A[i]<0) {
				Y-=min(Y,-A[i]);
				X+=-A[i];
			}
		}
		cout<<abs(X)+abs(Y)<<endl;
	}
}

まとめ

これはすんなり。