DDCC2019Final B - 大吉数列 (Array of Fortune) (600)

B - 大吉数列 (Array of Fortune)

概要

整数が与えられる。次の条件を満たす数列が存在すればその数列を1つ出力し、存在しなければNo Luckと出力せよ。

• 数列にはからまでの各数字がちょうど1回現れる
• を満たすの組（）がちょうど個存在する

制約

方針

極端な数列を考える。
数列は全てのについて、を満たすが存在しない。
また数列は全てのについて、を満たすが存在する。

後者の数列が各に対するの上限を与える。
すなわちなら（）、なら（）、のように計算される。

もし、与えられたがこの上限より大きければ、数列を構成できないためNo Luckとなる。
与えられたがこの上限以下であれば、数列を構成できる。

必要な数列はを加工していくことで構成できる。
の上限と与えられたとの差をremとし、remをにすることを考える。
と、そこからを先頭にしたを比較すると、
後者の方がを満たすの組の数が減る。
（の組がなくなるため）

よって数列を後ろから見てゆき、減らす組の数がrem以下であるなら、その数を移動させてremを減らす。
すでに移動された数がある場合、移動先を最後に移動させた数の直後にすると、remを増やすことがない。

解答

Submission #4046606 - DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll N, K, R;
	cin >> N >> K >> R;
 
	ll up[N+1];
	up[N] = 0;
	for(ll i = 1; i <= N; i++){
		up[N-i] = up[N-i+1] + i;
	}
 
	// for(ll k = 1; k <= N-1; k++){
	// 	cout << up[k] << " ";
	// }
	// cout << endl;
 
	if(R > up[K]){
		cout << "No Luck" << endl;
		return 0;
	}
 
	vector<ll> v;
	for(ll i = N; i >= 1; i--){
		v.push_back(i);
	}
 
	vector<ll> w;
	ll rem = up[K] - R;
	for(ll i = N-1; i >= 0; i--){
		if(i + 1 - K > 0 && rem - (i + 1 - K) >= 0){
			// cout << i << " " << rem << endl;
			w.push_back(N-i);
			rem -= i + 1 - K;
			v.erase(v.begin() + i);
		}
	}
 
	rep(i, w.size()){
		cout << w[i] << (v.size() == 0 ? "": " ");
	}
	rep(i, v.size()){
		cout << v[i] << ((i == v.size()-1) ? "": " ");
	}
	cout << endl;
}