解法1
考え方
例えば,入力例1を考えると,下図の筆算が計算できれば良い.繰り上がりを考えなければ,各桁の足し算は$X$の累積和になっている.
後は,繰り上がりを考慮すれば良い.
回答例
import itertools X = list(input()) X = list(map(int, X)) acc = list(itertools.accumulate(X)) acc.reverse() nxt = 0 ans = [] for x in acc: cur = x + nxt nxt, cur = divmod(cur, 10) ans.append(str(cur)) ans.reverse() nxt = '' if nxt == 0 else str(nxt) ans = nxt + ''.join(ans) print(ans)
累積和の部分は,ライブラリ使わなくても良い.
acc = [] prev = 0 for x in X: prev += x acc.append(prev)
解法2
考え方
次のように,各数字が現れる場所を追跡する.すると,- (1の位)×1
- (10の位)×(1+10)
- (100の位)×(1+10+100)
- (1000の位)×(1+10+100+1000)
- ・・・
\begin{aligned}
S_{i} = \text{($i$桁目)} \sum_{k=0}^{i-1} 10^{k}
\end{aligned}
であり,求めるものはこれらの和S_{i} = \text{($i$桁目)} \sum_{k=0}^{i-1} 10^{k}
\end{aligned}
\begin{aligned}
S = \sum_{i} S_{i}
\end{aligned}
である.S = \sum_{i} S_{i}
\end{aligned}
さて,$S_{i}$は等比級数の和であるから,
\begin{aligned}
& 10 S_{i} - S_{i} = \text{($i$桁目)} \times (10^{i} - 1) \\
&\Leftrightarrow S_{i} = \frac{ \text{($i$桁目)} \times (10^{i} - 1) }{9}
\end{aligned}
となる.よって,& 10 S_{i} - S_{i} = \text{($i$桁目)} \times (10^{i} - 1) \\
&\Leftrightarrow S_{i} = \frac{ \text{($i$桁目)} \times (10^{i} - 1) }{9}
\end{aligned}
\begin{aligned}
S
&= \sum_{i} S_{i} \\
&=\sum_{i} \frac{ \text{($i$桁目)} \times (10^{i} - 1) }{9} \\
&= \frac{10X - \sum_{i}\text{($i$桁目)}}{9}
\end{aligned}
で計算できる.S
&= \sum_{i} S_{i} \\
&=\sum_{i} \frac{ \text{($i$桁目)} \times (10^{i} - 1) }{9} \\
&= \frac{10X - \sum_{i}\text{($i$桁目)}}{9}
\end{aligned}
【参考】
回答例
X = input() X2 = list(map(int, X)) print((10 * int(X) - sum(X2)) // 9)