ARC173 A問題 を9進法の亜種で計算

上の問題の解き方を考えていたら、昨年学習したことを利用して解けたのでメモ。
ABC285 C問題：ゼロを使わないN進法についてのメモ - Qiita

解答

K を "bijective base-N numeration" という記数法（の N = 9）で表してから、各桁で用いる数字を「 0 〜 9 のうち一つ上の桁と被らないもの」に変える。テストケース毎の時間計算量は O(log K) 。

普段は Ruby を使っているが、最近勉強している Python で書いてみる。

Python

def num2str(num):
    digits = []
    while num > 0:
        num, d = divmod(num - 1, 9)
        digits.append(d + 1)
    digits.reverse()

    # bijective base-9 --> Neq Number
    for i in range(1, len(digits)):
        if digits[i] <= digits[i-1]:
            digits[i] -= 1

    return ''.join(map(str, digits))

t = int(input())
for i in range(t):
    k = int(input())
    print(num2str(k))

Ruby 版

Ruby

def num2str(num)
	digits = []
	while num > 0
		num, d = (num - 1).divmod(9)
		digits << d + 1
	end
	digits.reverse!

	# bijective base-9 --> Neq Number
	prev = 0
	digits.map! { |d| prev = (d > prev ? d : d - 1) }

	digits.join
end

t = gets.to_i
t.times do
	k = gets.to_i
	puts num2str(k)
end

発想の流れ

正整数 X ("Neq Number") の各桁の数字は、「最上位は1〜9」「他の桁は0〜9のうち一つ上の位のもの以外」であり、結局どの桁も9種類しか使えない。 d 桁の数なら 9^d 個だけ存在する。

どの桁も N 種類、かつ桁数によっても区別する（ゼロ埋めができない）という規則は、 bijective base-N numeration という記数法と一致する。これは、通常の位取り記数法は各桁で 0 〜 N-1 を使うのに対し、 1 〜 N を使うというもの。

今回の問題では N = 9 であり、 bijective base-9 numeration と X の違いは各桁に用いる数字だけと考えられる。

ひとまず色々な K 番目の数をこの記数法に直して X と比較してみる。問題文の入出力例やその説明にある数を試すと、以下の表のようになる。

K 番目	bijective	X
1	1	1
…	…	…
9	9	9
10	11	10
11	12	12
…	…	…
18	19	19
19	21	20
20	22	21
21	23	23
…	…	…
25	27	27
…	…	…
148	174	173
…	…	…
998244353	2516331732	2506230721
…	…	…

最後の複雑な例に関しても、 bijective base-9 numeration と X とでかなり似た値になっている。桁ごとに見ると、一致しているものと1だけ大きいものがある。どうも一つ上の桁より小さい数字については、1を減らす補正が必要らしい？

この補正は、各桁で使える9種類の数字が何かということに起因する。 bijective base-9 numeration では単純に 1〜9 を使う。一方で X では、例えば一つ上の位が 5 なら 0〜4 と 6〜9 を使う。素直に最上位の桁から順番に補正することもできるし、先ほどの予想のように各桁で並行して補正することもできる。
（訂正：最上位から始めずいきなり下の桁を補正することはできない。例えば bijective base-9 で 777 なら X は 767 というように、一見同じ数字の並びでも異なる補正になることがある。）

---

以上をまとめると解法は、 K を bijective base-9 numeration で表してから、各桁で用いる数字を「 0 〜 9 のうち一つ上の桁と被らないもの」に変える、ということになる。