各桁の和が 10 になる正の整数を「完全数」と呼びます(19,28,37,…)。小さい方から k 番目の完全数を求める問題です(1≤k≤105)。
完全数を小さい順にすべて列挙し、k 番目を出力します。
m=r+1 桁の完全数は、10 個の玉と r 本の仕切りを一列に並べたものと対応させられます。仕切りで区切られた r+1 個の区間に入っている玉の個数を、上の桁から順に並べたものが各桁の数字です。
たとえば r=2 で、12 マスの列のうち位置 3,7(0 始まり)に仕切りを置くと、各区間の玉の個数は 3,3,4 なので 334 を表します。
ただし、次の 2 つに注意します。
- 最上位の桁は 1 以上: 位置 0 に仕切りを置かなければよいので、仕切りの位置は 1,…,9+r から選びます。
- 各桁は 9 以下: 区間に玉が 10 個入る並べ方は数字として不正なので除きます。
桁数が少ないほど小さいので、r=1,2,… の順に列挙します。桁数が同じなら、仕切りの位置を辞書順に並べたものが数の小さい順と一致します。仕切りの位置が前にあるほど、上の桁が小さくなるからです。
r+1 桁の完全数は (r9+r)−1 個あり、11 桁(r=10)までで 184745 個になります。105 個を超えるので、r≤10 まで列挙すれば十分です。
Python
from itertools import combinations
for c in combinations(range(1, 10 + r), r=r):
ans.append(int("".join(map(str, l))))
combinations で仕切りの位置 c を辞書順に列挙しています。t は直前の仕切りの次の位置で、x - t が仕切りの間にある玉の個数、つまりその桁の数字です。最後の区間は列の長さ 10 + r までの玉の個数です。
桁に 10 があるものを除き、残りを数にして ans に入れていきます。