yukicoder : No.2025 Select k-th Submultiset

上限が変わってる問題。
https://yukicoder.me/problems/no/2025

問題

整数列Sが与えられる。Sは1～Nだけからなり、昇順に並んでいる。
Sの部分列のうち長さLのものを辞書順に並べたとき、K番目に来るものは何か。
なお、Sから抜き出した位置が異なっても、抜き出した値が同じ部分列は同じとみなす。

解法

f(n,l) := Sのうちn以上の値からなる長さlの数列の総数
を求めておこう。これはDPで計算できる。
あとは、1,2,3....と何個まで並べられた場合に構成できる数列がK通り以下に収まるか、順次二分探索を繰り返していけばよい。

int N,L;
int C[4];

ll dp[5][102010];
ll S[5][102010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L;
	FOR(i,N) cin>>C[i];
	
	dp[N][0]=1;
	FOR(i,101010) S[N][i]=1;
	for(j=N-1;j>=0;j--) {
		FOR(i,101010) {
			dp[j][i]=S[j+1][i];
			if(i>C[j]) dp[j][i]-=S[j+1][i-C[j]-1];
			
			S[j][i]=dp[j][i];
			if(i) S[j][i]+=S[j][i-1];
		}
	}
	
	int Q;
	cin>>Q;
	while(Q--) {
		ll K;
		cin>>K;
		
		if(dp[0][L]<K) {
			cout<<-1<<endl;
			continue;
		}
		
		int cur=L;
		int R[4]={};
		FOR(i,N) {
			int ma=min(cur,C[i]);
			for(j=20;j>=0;j--) if(ma>=(1<<j)) {
				ll su=S[i+1][cur-(ma-(1<<j))-1]-S[i+1][cur-ma-1];
				if(su<K) {
					K-=su;
					ma-=1<<j;
				}
			}
			
			R[i]=ma;
			cur-=ma;
			cout<<R[i]<<" ";
		}
		cout<<endl;
		
	}
	
}

まとめ

確かに数列といいつつmultisetだな。