Cまで簡単だったようで、3完したのにレート下がった。
https://codeforces.com/contest/1396/problem/A
問題
整数列Aが与えられる。
この整数列に、以下の処理を3回行い、値を0にせよ。
- 区間[L,R]を選ぶA[L,R]それぞれに、区間長の倍数を加算する。(加算する値は、要素毎に変えてよい)
解法
N=1なら、初手で-A[0]を加算し、あとは0を2回加算してしまえばよい。
そうでない場合、まず初手で全区間を選択肢、i番目の要素にはそれぞれ-A[i]*Nを加算する。
すると各要素-A[i]*(N-1)となるので、いずれも(N-1)の倍数になる。
そこで2回目は[0,N-2]を選択して各要素0にし、3回目は[1,N-1]か[N-1,N-1]を選択してA[N-1]を0にすればよい。
int N; ll A[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i]; if(N==1) { cout<<"1 1"<<endl; cout<<-A[0]<<endl; cout<<"1 1"<<endl; cout<<0<<endl; cout<<"1 1"<<endl; cout<<0<<endl; return; } cout<<"1 "<<N<<endl; FOR(i,N) { cout<<-A[i]*N; if(i!=N-1) cout<<" "; } cout<<endl; cout<<"1 "<<(N-1)<<endl; FOR(i,N-1) { if(i==0) cout<<A[i]*(N-1); else cout<<0; if(i!=N-1) cout<<" "; } cout<<endl; cout<<"2 "<<N<<endl; FOR(i,N-1) { cout<<A[i+1]*(N-1); if(i!=N-1) cout<<" "; } cout<<endl; }
まとめ
Div2Bでも良いぐらいの問題。