コンテンツにスキップ

SamCoding Round 7 (Div. 2) D - Perfect Number

サイト
SamCoding
コンテスト
SamCoding Round 7 (Div. 2)
問題
D - Perfect Number(常設版)

各桁の和が 1010 になる正の整数を「完全数」と呼びます(19,28,37,…19, 28, 37, \ldots)。小さい方から kk 番目の完全数を求める問題です(1≤k≤1051 \le k \le 10^5)。

完全数を小さい順にすべて列挙し、kk 番目を出力します。

m=r+1m = r + 1 桁の完全数は、1010 個の玉と rr 本の仕切りを一列に並べたものと対応させられます。仕切りで区切られた r+1r + 1 個の区間に入っている玉の個数を、上の桁から順に並べたものが各桁の数字です。

たとえば r=2r = 2 で、1212 マスの列のうち位置 3,73, 7(00 始まり)に仕切りを置くと、各区間の玉の個数は 3,3,43, 3, 4 なので 334334 を表します。

ただし、次の 2 つに注意します。

  • 最上位の桁は 11 以上: 位置 00 に仕切りを置かなければよいので、仕切りの位置は 1,…,9+r1, \ldots, 9 + r から選びます。
  • 各桁は 99 以下: 区間に玉が 1010 個入る並べ方は数字として不正なので除きます。

桁数が少ないほど小さいので、r=1,2,…r = 1, 2, \ldots の順に列挙します。桁数が同じなら、仕切りの位置を辞書順に並べたものが数の小さい順と一致します。仕切りの位置が前にあるほど、上の桁が小さくなるからです。

r+1r + 1 桁の完全数は (9+rr)−1\binom{9 + r}{r} - 1 個あり、1111 桁(r=10r = 10)までで 184745184745 個になります。10510^5 個を超えるので、r≤10r \le 10 まで列挙すれば十分です。

Python
from itertools import combinations
ans = []
for r in range(1, 11):
for c in combinations(range(1, 10 + r), r=r):
t = 0
l = []
for x in c:
l.append(x - t)
t = x + 1
l.append(10 + r - t)
if 10 in l:
continue
ans.append(int("".join(map(str, l))))
K = int(input())
print(ans[K - 1])

combinations で仕切りの位置 c を辞書順に列挙しています。t は直前の仕切りの次の位置で、x - t が仕切りの間にある玉の個数、つまりその桁の数字です。最後の区間は列の長さ 10 + r までの玉の個数です。

桁に 10 があるものを除き、残りを数にして ans に入れていきます。