yukicoder : No.2934 Digit Sum

意外にコードが短い。
https://yukicoder.me/problems/no/2934

問題

整数N,Kが与えられる。
各桁の総和がN以下の正整数のうち、小さい順にK番目のものを求めよ。
なお、解は10^5桁以下である問題しか出ない。

解法

Nは162以下まで考えればよい。
各桁の総和が163となる最小値はKより大きいため。

dp(d,n) := d桁以下の整数のうち、各桁の総和がn以下である者の個数。
としてこのテーブルを埋め、上の桁から埋めて行けばよい。

__int128 dp[101010][170];
ll N,K;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>K;
	N=min(N,163LL);
	K++;
	FOR(i,N+1) dp[0][i]=1;
	FOR(i,101000) {
		FOR(x,N+1) FOR(y,10) if(x+y<=N) dp[i+1][x+y]+=dp[i][x];
		__int128 sum=dp[i+1][N];
		if(sum>=K) {
			int cur=i+1;
			while(cur>0) {
				FOR(x,10) {
					if(dp[cur-1][N-x]>=K) {
						cout<<x;
						N-=x;
						break;
					}
					else {
						K-=dp[cur-1][N-x];
					}
				}
				cur--;
			}
			cout<<endl;
			return;
		}
	}
}

まとめ

Editorialだとテーブルがもう1次元多いんだよな…。