Codeforces #666 Div1 A. Multiples of Length

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でも良いぐらいの問題。