Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 142 A問題 Reverse and Minimize

AtCoder ARC ARC142 A問題 300 pts

問題

提出解答

問題の概要

正の整数 $x$ に対して, $f(x)$ を次のように定める.

$g^{(0)}(x):=x$
$g^{(k)}(x)$ を次のようにして定める: $g^{(k-1)}(x)$ の十進表記を左右反転して, 先頭の $0$ を削除できるだけ削除した整数を $g^{(k)}(x)$ とする.
$\displaystyle f(x):=\min_{0 \leq k} g^{(k)}(x)$

$1 \leq x \leq N$ となる整数のうち, $f(x)=K$ を満たす整数はいくつか?

制約

$1 \leq N \leq 10^{12}$
$1 \leq K \leq 10^{12}$

解法

$g^{(k)}(x)$ の作り方から,

$g^{(1)}(x)=g^{(3)}(x)=\dots=g^{(2t-1)}(x)=\dots$
$g^{(2)}(x)=g^{(4)}(x)=\dots=g^{(2t)}(x)=\dots$

である. また, $g^{(2)}(x)$ は $x$ の先頭から $0$ を取り除けるだけ取り除いた整数なので, $x=g^{(0)}(x) \geq g^{(2)}(x)$ である.

よって,

$f(x)=\min \left(g^{(1)}(x), g^{(2)}(x) \right)$

である.

ここからは計上にはいる. まず, $f(K) \neq K$ であるときは上で述べた理由により, $0$ 個である. $f(K)=K$ であるとき, $f(x)=K$ となるような整数の候補は

$K, 10K, 10^2 K, \dots$
$g^{(1)}(K), 10 g^{(1)}(K), 10^{2} g^{(1)}(K), \dots$

である. そして, これらの候補は全て $f(x)=K$ となる.

よって, これらの整数のうち, $N$ 以下であるような整数の個数を重複に注意して求めれば良い. 計算量は $O(\log N)$ である.