🌊

ABC192 D - Base n

2021/02/22に公開

競技プログラミング

tech

問題概要

'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+1$ で $M$ を超えるため、上限は $M+1$ に設定する

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

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

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

不等式を式変形する

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

問題概要

解法

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

不等式を式変形する

Discussion