DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 : B - 大吉数列 (Array of Fortune)

これが２問目にあるのはしんどいなぁ。
https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_b

問題

整数N,K,Rが与えられる。
1～NのPermutationのうち、A[i]≧A[j]+Kを満たすi＜jがR通りであるものを構築せよ。

解法

大雑把に決めた後、微調整する方針で行く。
(N,N-1,...,N-p+1,1,2,...,p)となる数列において、上記の条件がR通り近くなるものを二分探索で求めよう。
あとはN-p-1を後ろのものと1個ずつswapしていけば条件を満たす組み合わせを1つずつ増やせる。

int N,K;
ll R;
ll hoge(int p) {
	ll ret=0;
	int i;
	for(i=1;i<=N;i++) {
		ret+=max(0,N-(max(i+K,p+1)-1));
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>R;
	if(R==0) {
		for(i=1;i<=N;i++) cout<<i<<" ";
		cout<<endl;
		return;
	}
	
	
	ll v=hoge(1);
	if(R>v) return _P("No Luck\n");
	if(R==v) {
		for(i=N;i>=1;i--) cout<<i<<" ";
		cout<<endl;
		return;
	}
	
	int p=1;
	for(i=20;i>=0;i--) {
		if(p+(1<<i)>=N) continue;
		if(hoge(p+(1<<i))>=R) p+=1<<i;
	}
	
	vector<int> V;
	for(i=N;i>=p+1;i--) V.push_back(i);
	for(i=1;i<=p;i++) V.push_back(i);
	R-=hoge(p);
	for(i=N-p-1;R;i++) {
		if(V[i+1]+K<=V[i]) {
			R++;
		}
		swap(V[i+1],V[i]);
	}
	
	FORR(v,V) cout<<v<<" ";
	cout<<endl;
	
	
}

まとめ

色んな構築法が考えられそう。