Kazun の競プロ記録

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

AtCoder Beginner Contest 238 C問題 digitnum

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

 f(x) を以下を満たす正の整数の個数とする.

  •  x 以下
  •  x と桁数が等しい.

このとき,  \displaystyle \sum_{x=1}^N f(x) を求めよ.

制約

  •  1 \leq N \lt 10^{18}

解法

 x d 桁の整数のとき,  f(x)=x-10^{d-1}+1 である. よって,  N r 桁の整数であるとすると,

 \displaystyle \begin{align*}
\sum_{x=1}^N f(x)
&=\sum_{d=1}^{r-1} \sum_{x=10^{d-1}}^{10^d-1} f(x)+\sum_{x=10^r}^N f(x) \\\\
&=\sum_{d=1}^{r-1} \sum_{x=10^{d-1}}^{10^d-1} (x-10^{d-1}+1) +\sum_{x=10^r}^N (x-10^{r-1}+1) \\\\
&=\dfrac{9}{2} \sum_{d=1}^{r-1} 10^{d-1} (9\times 10^{d-1}+1) +\dfrac{1}{2} (N-10^{r-1}+1)(N-10^{r-1}+2)
\end{align*}

である.

ここから更に式変形を進めてもよいが,  N \lt 10^{18} より,  r \leq 18 なので, この総和をそのまま計算することで答えを導くことができる.

ちなみに,

 \displaystyle \sum_{x=1}^N f(x)=\dfrac{(10^{r-1}-1)(9 \times 10^{r-1}+20)}{22}+\dfrac{1}{2} (N-10^{r-1}+1)(N-10^{r-1}+2)

である.