🌊

ABC192 D - Base n

2021/02/22に公開

問題概要

'0'~'9'からなる文字列Xをn(n \ge d+1)(dはXの中で一番大きい数字)進数とみたときに、
その値がM以下になるものは何通りあるか

解法

Xを

d_i d_{i-1} d_{i-2} ... d_1とおくと

n進数とみたときにその値は

d_i \times n^{i-1} + d_{i-1} \times n^{i-2} + ... + d_1 \tag{1}

となる

Xが一桁か二桁以上かでは話が変わってくる

  • Xが一桁のとき

このときXを何進数とみたところでその値が変わることはなく
XがM以下なら1通り、XがMより大きい場合は0通り

  • Xが二桁以上のとき

(1)式がnの値に対して単調増加になるのは明らかで
異なるnの値に対して異なる値をとる
よって、この値がM以下となるようなnの個数を数えればいい

d_i \times n^{i-1} + d_{i-1} \times n^{i-2} + ... + d_1 \le M

という条件を考えたときに左辺は単調増加であることから、単調性が成り立ち、
二分探索を用いて答えを求めることができる

M以下になるようなnが一つも存在しない場合があるため、下限はdに設定する
二桁以上のXの中で最小のものは"10"であり、このときn = M+1Mを超えるため、上限はM+1に設定する

ただし、愚直に(1)式を計算してしまうとオーバフローが問題になる
いかにしてオーバフローを回避するかということを考える必要がある

言語のもつオーバフロー検知の機能を使う

言語によってはオーバフローを検知する機能をもっているのでそれを使う

https://atcoder.jp/contests/abc192/submissions/20340266

不等式を式変形する

v = 0として
v = vn + d_jj = i..1まで計算するとXをn進数としてみたときの値を計算できる
このとき、vn \gt Mならば値が既にMを超えているので計算を打ち切ることにする
オーバフローを避けるため両辺をnでわって、v \gt \frac{M}{n}
vは整数であるのでv \gt \lceil \frac{M}{n} \rceil
この条件を使って超えたかどうかを判定する

https://atcoder.jp/contests/abc192/submissions/20413036

Discussion