Kazun の競プロ記録

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

AtCoder Regular Contest 144 A問題 Digit Sum of 2x

AtCoder ARC ARC144 A問題 300 pts

問題

提出解答

問題の概要

正の整数 $x$ に対して, $f(x)$ で $x$ の桁和を表すとする.

以下の2つの整数 $M,x$ を求めよ.

$\displaystyle M=\max \{f(2x) \mid x \in \mathbb{Z}_{\gt 0},~f(x)=N\}$
$\displaystyle x=\min \{y \in \mathbb{Z}_{\gt 0} \mid f(y)=N, f(2y)=M\}$

制約

$1 \leq N \leq 10^5$

解法

正の整数 $x$ において, $5,6,7,8,9$ である桁の数を $k$ としたとき, $f(2x)=2f(x)-9k \cdots (*)$ である. よって, $f(x)=N$ ならば, $f(2x)=2N-9k \leq 2N$ である. そして, $x=\dfrac{10^N-1}{9}=\underbrace{1 \dots 1}_{N}$ のときは $f(2x)=2N$ である. よって, $M=2N$ である.

$f(y)=N, f(2y)=2N$ となる最小の正の整数 $y$ を求める. このような $y$ は $(*)$ から, 各桁は $0,1,2,3,4$ のいずれかである. そして, $y$ に $0$ である桁が存在する場合, その桁を削除することにより, 桁和を変えずに $y$ を小さくできる. よって, 各桁は $1,2,3,4$ のいずれかであるとしてよい.

$y$ にある $1,2,3,4$ である桁の数を順に $a,b,c,d$ とすると,

$f(y)=a+2b+3c+4d=N$
$f(2y)=2a+4b+6c+8d=2N=M$

となるが, 下の式は上の式の2倍で得られるので, 上の式にのみ着目すれば良い.

$y$ を最小にするためには桁数を最小にしなけえればならない. これは $a+b+c+d$ を最小にすることを意味する. この最小値は $\left \lceil \dfrac{N}{4} \right \rceil$ である. 実際, $N$ を $4$ で割った商と余りを $q,r$ としたとき,

$r=0$ のとき, $(a,b,c,d)=(0,0,0,q)$
$r=1$ のとき, $(a,b,c,d)=(1,0,0,q)$
$r=2$ のとき, $(a,b,c,d)=(0,1,0,q)$
$r=3$ のとき, $(a,b,c,d)=(0,0,1,q)$

とすれば $a+b+c+d=\left \lceil \dfrac{N}{4} \right \rceil$ である. これが最小になることも簡単に示せる.

最小となる $y$ における $1,2,3,4$ の桁の個数がこれで分かった. これを並び替えて最小にするためには,

$r=0$ のとき, $y=\underbrace{4 \dots 4}_{q}$
$r=1$ のとき, $y=1\underbrace{4 \dots 4}_{q}$
$r=2$ のとき, $y=2\underbrace{4 \dots 4}_{q}$
$r=3$ のとき, $y=3\underbrace{4 \dots 4}_{q}$

となる.