Codeforces #715 Div1 : B. Almost Sorted

これはまぁ典型かな…。
https://codeforces.com/contest/1508/problem/B

問題

順列Aがほぼソートされているとは、A[i+1]≧A[i]-1であることを意味する。

整数N,Kが与えられる。
ほぼソートされた1～Nの順列のうち、辞書順でK番目に来るものを答えよ。

解法

ほぼソートされた数列は、1ずつ降下する部分列を連結した数列となる。
先頭何要素を降順にするかを考えると、
dp(n) := 1～nの順列のうち、ほぼソートされたものの数
とすると
dp(n) = 1+sum(dp(m)) (m＜n)
となる。

よって、最初にdp(n)を求めておき、あとは合計がKを超えないよう、先頭から何要素降順に並べるかを見ていこう。

int T;
int N;
ll K;
ll dp[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=100000;i++) {
		dp[i]=1;
		for(j=1;j<i;j++) {
			dp[i]+=dp[j];
			if(dp[i]>=1LL<<60) {
				dp[i]==1LL<<60;
				break;
			}
		}
	}
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		if(K>dp[N]) {
			cout<<-1<<endl;
			continue;
		}
		
		vector<int> V;
		for(i=1;i<=N;) {
			for(j=1;i+j<=N;j++) {
				if(dp[N-(i-1)-j]<K) {
					K-=dp[N-(i-1)-j];
				}
				else {
					break;
				}
			}
			FOR(x,j) V.push_back(i+j-1-x);
			i+=j;
		}
		FORR(v,V) cout<<v<<" ";
		cout<<endl;
	}
}

まとめ

本番もまぁまぁすんあり解いてるな。