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; } } }
まとめ
似た問題見てそうだ。