https://kotamanegi.com/Problems/view/index.php?page=72
解法
1. この手の構築問題にはテクがある
2. 「①最上位の数と桁数を決定する②上位桁から順番に数を決定していく」というテク
3. このテクを使うには組み合わせ数を適切に計算する必要があるが、再帰を使えば実現できる
解法
https://kotamanegi.com/Submission/view/index.php?SubmissionID=1755
「①最上位の数と桁数を決定する②上位桁から順番に数を決定していく」というテクで解ける構築。
このテクではK番目は0-indexedにするのが常套。
①最上位の数と桁数を決定する
小さい方から順番に組み合わせ数を数える
「1」「2」…「9」「1?」「2?」…「9?」「1??」「2??」…のように組み合わせ数を考える。
例えば、「1??」の組み合わせ数は??に数を入れて桁和がNとなる組み合わせ数である。
これをcmb関数で求める。
cmb(d,sm) := d桁分0～9を埋めて桁和がsmとなる組み合わせ数
これは再帰を使えば計算できる。
あとは、何回も呼び出されるのでメモ化をしておこう。
d桁で先頭の数がnである桁和がNである組み合わせ数はcmb(d-1,N-n)である。
もし、cmb(d-1,N-n)≦Kであれば、このパターン内にK番目が収まらないので、次の数を見る。
次の数を見るときはK -= cmb(d-1,N-n)として、先頭をずらしながら行っていく。
②上位桁から順番に数を決定していく
phase2関数で行う。
上位桁から数を決定していくが、①とほぼ同様。
組み合わせ数もcmb関数で求めていく。
int N, K; //--------------------------------------------------------------------------------------------------- #define CMAX 1010 ll memo[CMAX][CMAX]; int vis[CMAX][CMAX]; ll cmb(int d, int sm) { if (d < 0 or sm < 0) return 0; if (d == 0) { if (sm == 0) return 1; else return 0; } if (vis[d][sm]) return memo[d][sm]; ll res = 0; rep(i, 0, 10) res += cmb(d - 1, sm - i); vis[d][sm] = 1; return memo[d][sm] = res; } //--------------------------------------------------------------------------------------------------- void phase2(int d, int n) { printf("%d", n); N -= n; rrep(dd, d - 1, 2) rep(nn, 0, 10) { ll cnt = cmb(dd - 1, N - nn); if (cnt <= K) K -= cnt; else { printf("%d", nn); N -= nn; break; } } if(1 < d) printf("%d\n", N); else printf("\n"); } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> K; K--; rep(d, 1, 1010) rep(n, 1, 10) { ll cnt = cmb(d - 1, N - n); if (cnt <= K) K -= cnt; else { phase2(d, n); return; } } }
