Official
E - Σ[k=0..10^100]floor(X/10^k) Editorial by physics0523
まず、 \(X < 10^{500000}\) という制約に注目しましょう。この値は通常の整数型として管理するにはとても大きすぎます。
なので、この問題は \(X\) を文字列として受け取って解く必要があります。
求める値がどのようなものか、 \(X=123456\) の具体例を用いて検討しましょう。
各項を横に並べてもよく分からないので、(\(1\) 以上の)各項を縦に並べて筆算のような形で書いてみましょう。ただし、各項の小数点以下を切り捨ててから足し合わせることに注意してください。
123456
12345 .6
1234 .56
123 .456
12 .3456
+ 1 .23456
-------
137171
ここで、「和の下から \(k\) 桁目には、 \(X\) の最も上の位から下から \(k\) 桁目までが足されている」ことが見て取れます。 実際、先ほどの筆算に以下のような計算過程を書き足すことができます。
123456
12345
1234
123
12
+ 1
-------
21
15
10
6
3
+1
-------
137171
これを(繰り上がりも含めて)上手く実装する必要があります。
実装の方針はいくつかあると思われますが、ひとつの方針として、大まかに以下の手順で下の位から決定していくことができます。
- \(s\) を \(X\) の桁和、 \(c=0\) として初期化する。
- \(c\) に \(s\) を加算する。
- 答えのうち現在着目している桁を、 \(c\) を \(10\) で割った余りとして確定させる。
- \(c\) を \(10\) で割り小数点以下を切り捨てる。ここが繰り上がりに対応する。
- \(s\) から \(X\) の現在着目している桁の値を引き去る。(ただし、そのようなものがなければ引き去る値を \(0\) とする。) この時点で、 \(s\) は \(X\) の先頭の桁から現在着目している桁のひとつ上の桁までの桁和となる。
- \(X\) の桁をすべて消化して、かつ \(c=0\) となるまで 2. から 5. の流れを繰り返す。
実装例(C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
string x;
cin >> x;
int s=0,c=0;
for(auto &nx : x){s+=(nx-'0');}
string res;
for(int i=x.size()-1;;i--){
c+=s;
res.push_back('0'+(c%10));
c/=10;
if(i>=0){s-=(x[i]-'0');}
if(i<=0 && c==0){break;}
}
reverse(res.begin(),res.end());
cout << res << '\n';
return 0;
}
posted:
last update: