Ozon Tech Challenge 2020 : E. Kuroni and the Score Distribution

レート微減だった回。
https://codeforces.com/contest/1305/problem/E

問題

整数N,Mが与えられる。
N要素の昇順な正整数列Aのうち、A[i]+A[j]=A[k]を満たす(i,j,k)の組がちょうどM個になるようなAを構築せよ。

解法

先頭n要素まで決めたとき、最大値がyだったとする。
次のp要素にy～(y+p-1)を並べ、その次に(2*y+p-1)を置けば、C(p,2)通りだけ条件を満たす組を作れる。
そこで総数がMに近づくように大きい順にpを選んでいこう。

int N;
int M;
int R[5050];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	FOR(i,N) {
		if(i<2) {
			R[i]=i+1;
		}
		else {
			if(M==0) {
				R[i]=1000000000-100000*(N-i);
			}
			else {
				int num=min(i/2,M);
				M-=num;
				if(num==i/2) {
					R[i]=R[i-1]+1;
				}
				else {
					R[i]=(i+1)-1+(i+1)-num*2;
				}
			}
		}
	}
	if(M>0) {
		cout<<-1<<endl;
	}
	else {
		FOR(i,N-1) assert(R[i]<R[i+1]);
		assert(R[0]>=1 && R[0]<=1000000000);
		assert(R[N-1]>=1 && R[N-1]<=1000000000);
		FOR(i,N) cout<<R[i]<<" ";
		cout<<endl;
	}
		
	
}

まとめ

色んな構築法があるかな？