競技プログラミング日記

主に AtCoder の記事です

AtCoder Beginner Contest 233E

ABC233E

実際に手を動かしてみると, 各桁ごとの累積和を計算すれば良いことに気づく.

実装:
数字を文字列で扱う.
繰り上がりに注意. また,繰り上がりが発生すると,最初に与えられた \(x\) の桁よりも ずっと答えの桁が大きくなる可能性がある.
繰り上がりが有る限り計算を続けて, 繰り上がりが無くなれば終わり.
文字列で数字を扱うとき,vector や string を reverse するのを忘れない.

使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {
  string s; cin >> s;
  ll n = s.length();

  ll t = 0;
  vll v(n);
  rep(i,n){
    t += s[i]-'0';
    v[i] = t;
  }
  reverse(all(v));

  string ans;
  rep(i,v.size()){
    ans.push_back(v[i]%10 + '0');
    ll q = v[i]/10;
    if(q > 0){
      if(i+1 >= v.size()) v.push_back(0);
      v[i+1] += q;
    }
  }
  reverse(all(ans));
  cout << ans << endl;

  return 0;
}