ABC233_E – Σ[k=0..10^100] floor(X／10^k)

問題

E - Σ[k=0..10^100]floor(X／10^k)

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

提出

Submission #44922223 - AtCoder Beginner Contest 230

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

3回目くらいで解けた

以下、解法を書く。

入力例1を参考にすると、以下の数字を足すのが目的となる。
$1225+122+12+1$
Xが大きいので愚直に計算はできない。
そこで、一桁ずつ足すことを考えてみる。
上記の例で一桁目だけ足してみると、以下のようになる。
$5+2+2+1=10$
つまり、答えの1桁目は0になる。
2桁目は、1桁目の繰り上がりも考慮して、以下のようになる。繰り上がりは括弧を使って書く。
$(1)+2+2+1=6$
3桁目は以下のようになる。
$(0)+2+1=3$
4桁目は以下のようになる。
$(0)+1=1$

これらを並べると、4桁目から並べると1360となる。
これを愚直に計算したとしても、計算回数が多く間に合わない。
それぞれの桁の和を見てみると、1225の累積和と繰り上がりの和になっている。
累積和をあらかじめ計算しておくと、各桁の和は$O(1)$で計算できる。
累積和を以下のように計算する。
$acc[0]=0$
$acc[1]=X[0]=1$
$acc[2]=X[0]+X[1]=1+2$
$acc[3]=X[0]+X[1]+X[2]=1+2+2$
$acc[4]=X[0]+X[1]+X[2]+X[3]=1+2+2+5$

累積和を用いて、上記を書き直すと、以下のようになる。
$1桁目:(0)+acc[4]=10$
$2桁目:(1)+acc[3]=6$
$3桁目:(0)+acc[2]=3$
$4桁目:(0)+acc[1]=1$
$5桁目:(0)+acc[0]=0$

5桁目は4桁目に繰り上がりがある場合のみ値を入れる。