Codeforces #681 Div1 A. Extreme Subtraction

3問解いてほぼレート通りの結果。
https://codeforces.com/contest/1442/problem/A

問題

正整数列Aが与えられる。

• prefix何要素かをデクリメントする
• suffix何要素かをデクリメントする

の処理を任意回数繰り返し、Aの全要素を0にできるか判定せよ。

解法

Aを非負整数の単調増加列Bと単調減少列Cの和としてA[i]=B[i]+C[i]となるように分解できればよい。
A[-1]=B[-1]=inf, C[-1]=0として、以下の手順でB[i]・C[i]を埋めて行こう。

• A[i]＞A[i+1]ならC[i]-C[i+1]=A[i]-A[i+1]、B[i]=B[i+1]
• A[i]＜A[i+1]ならB[i]-B[i+1]=A[i]-A[i+1]、C[i]=C[i+1]

B[i]・C[i]が非負整数なら良い。

int T;
int N,A[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>A[i];
		x=1<<20,y=0;
		FOR(i,N) {
			if(A[i]>x+y) {
				y+=A[i]-(x+y);
			}
			else {
				if(A[i]>=y) {
					x=A[i]-y;
				}
				else {
					break;
				}
			}
			
		}
		if(i<N) {
			cout<<"NO"<<endl;
		}
		else {
			cout<<"YES"<<endl;
		}
	}
}

まとめ

似た問題見てそうだ。