ABC-387 C - Snake Numbers
https://atcoder.jp/contests/abc387/tasks/abc387_c
350点のC問題はいつも警戒してしまうんですが、今回も例に漏れず難問でした。60分以上かかりましたが、問題との相性が良かったのか運良く正解できました。解けて気分がよかったので解説記事を書いてみました。
コンテスト中の自分の動き
途中で諦めてD問題にも挑みましたがそちらも解けるかどうか怪しく、C・Dどちらに残り時間(45分ほど)を費やすか悩み、そしてこのC問題を選びました。理由としてはグリッド問題よりも整数問題の方が手元での検証がやりやすいこと、ヘビ数の法則自体はわかっていて残りの問題は実装だけだったことが挙げられます。腹をくくってABC3完を目標に据え、落ち着いて時間をかけて取り組むことにしました。最終的にはDも解決できてめでたく4完&自身2度目の水パフォ達成となりました。2完になってもおかしくなかったです。
法則を考える
10から順にヘビ数を書き出してみます。
2桁の場合
- 10
- 20, 21
- 30, 31, 32
......
十の位の数を d とすると、d 個ずつ並びます。合計値は Σd 。
3桁の場合
- 100
- 200, 201, 210, 211
- 300, 301, 302, 310, 311, 312, 320, 321, 322
- 400, 401, 402, 403, 410, ......
......
百の位の数を d とすると d^2 個ずつ並びます。合計値は Σ d^2 。
書き出してみると N 桁の場合、一番上の位の数字を d とすると下 N-1 桁に使われるのは 0 から d-1 の d 種類の数字で、つまり d 進数です。下 N-1 桁には d 種類の数字を使って作れる全ての数字が並ぶので、これを 10 進数に変換すれば「あるヘビ数がその桁数のヘビ数の中で小さい方から何番目であるか」がわかるようになります。例えば 4321 なら 4桁の中で 1xxx が 1 個、2xxx が 8個、3xxx が 27個あり、4進数 321 を10進数に変換すると 57 なので全部足せば OK です。
N 進数に変換しなくてもこの桁についてはこれより小さな数が何個あって……みたいに数えてもできますがかなり複雑です。最初それでやった際、与えられた L, R がヘビ数であるとは限らないと気づいていなかったこともあり沼にはまりました。
解き方
ヘビ数が与えられたときに何番目であるのかはこの考え方で求められますが、与えられた L, R がヘビ数であるとは限りません。L , R 以上で最小のヘビ数をそれぞれ求めます。最上位の数字を d として、2桁目から順に見ていって d 以上の数字が現れたらそれ以降を全て 0 にし、最後に見ていた桁の 1 つ前に 1 を加えます。得られたヘビ数をそれぞれ LL, RR とします。
LL, RR がそれぞれ小さい方から数えて何番目のヘビ数であるのかを求めます。何桁のヘビ数が何個あるのかは容易に求められますし、その桁の中で何番目であるのかは先の考え方からすぐにわかります。
最後に「RR が何番目か」から「LL が何番目か」を引けば終わりです。R 自身がヘビ数だった場合 +1 個すればいいです。
実装
# n 進数を 10 進数に変換する
def base_n_to_10(n, string):
string = string[::-1]
n10 = 0
for digit in range(len(string)):
n10 += n ** digit * int(string[digit])
return n10
# 桁数ごとに何個あるかをまず求めておく。19桁まで計算しておく。
count_by_digit = [0 for _ in range(20)]
for digit in range(2, 20):
total = 0
for num in range(1, 10):
total += num ** (digit - 1)
count_by_digit[digit] = total
# 使いやすくするため、累積和にして持っておく。
cum = [0 for _ in range(20)]
for i in range(1, 20):
cum[i] = cum[i-1] + count_by_digit[i]
# 入力
L, R = input().split()
# L 以上の最小のヘビ数を求める。
LL = int(L[0])
for i in range(1, len(L)):
if int(L[0]) <= int(L[i]):
LL += 1
LL *= 10 ** (len(L) - i)
break
else:
LL = LL * 10 + int(L[i])
LL = str(LL)
# R 以上の最小のヘビ数を求める。
RR = int(R[0])
for i in range(1, len(R)):
if int(R[0]) <= int(R[i]):
RR += 1
RR *= 10 ** (len(R) - i)
break
else:
RR = RR * 10 + int(R[i])
RR = str(RR)
# LL が何番目であるのかを調べる。1 桁目を d とすると 2 桁目以降は d 進数の数になる。
d = int(LL[0])
order_L = base_n_to_10(d, LL[1:]) + 1 # 2 桁目以降を 10 進数に変換して何番目かを調べる。
for i in range(1, d): # 1 桁目が 1 から d-1 であるヘビ数の数を数える。
order_L += i ** (len(LL) - 1)
order_L += cum[len(LL) - 1] # 桁数の少ない分を足す。
## RR についても同様。
d = int(RR[0])
order_R = base_n_to_10(d, RR[1:]) + 1
for i in range(1, d):
order_R += i ** (len(RR) - 1)
order_R += cum[len(RR) - 1]
ans = order_R - order_L
if R == RR: # R 自身がヘビ数だったら 1 個余分に数える。
ans += 1
print(ans)