けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 379 E - Sum of All Substrings (1D, 水色, 475 点)

AtCoder AtCoder475点 ABC-E 水色diff NoviSteps1D 解空間:O(N^2)個の区間 解空間:O(N^2)通りの選択肢 総和を求める 主客転倒・寄与分解

「主客転倒・寄与分解」の典型問題！

問題概要

1 から 9 までの数字からなる N 桁の整数値 S が与えられる。

この整数値の連続する区間を取り出してできる整数値の総和を求めよ。（998244353 で割らない。）

制約

  • 1 \le N \le 2 \times 10^{5}

考えたこと

この手の問題では、 S の各桁の値について「何回足されるのか」を考えるのが定石だ。たとえば、 S = "4649" としてみよう。このとき、

  • 最初の 4 は、"4", "46", "464", "4649" について、それぞれ 1 倍、10 倍、100 倍、1000 倍にして足されると考えて、1111 倍
  • 次の 6 は、"6", "46", "64", "464", "649", "4649" について、それぞれ 1 倍、1 倍、10 倍、10 倍、100 倍、100 倍にして足されると考えて、222 倍
  • 次の 4 は、"4", "64", "464", "49", "649", "4649" について、それぞれ 1 倍、1 倍、1 倍、10 倍、10 倍、10 倍にして足されると考えて、33 倍
  • 次の 9 は、"9", "49", "649", "4649" について、それぞれ 1 倍、1 倍、1 倍、1 倍にして足されると考えて、4 倍

となる。よって、答えは

4 × 1111 + 6 × 222 + 4 × 33 + 9 × 4

となる。これを少し整理すると

(4 × 1) × 1000
+ (4 × 1 + 6 × 2) × 100
+ (4 × 1 + 6 × 2 + 4 × 3) × 10
+ (4 × 1 + 6 × 2 + 4 × 3 + 9 × 4) × 1

と表現できる。ここまで分かれば、容易に一般化できる。

多倍長整数ライブラリがなくても

上記の結果は、十進法の各桁の値が概ね求まる形になっているので、繰り上がりをきちんと考慮してあげれば、多倍長整数ライブラリがなくても計算できる。

計算量は O(N) と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;
    string S;
    cin >> N >> S;

    // 各桁の和を求めておく
    vector<long long> res;
    long long sum = 0;
    for (int i = 0; i < N; i++) {
        sum += (long long)(S[i] - '0') * (i + 1);
        res.push_back(sum);
    }

    // 繰り上がり加味しながら足していく
    long long kuriagari = 0;
    for (long long i = N-1; i >= 0; i--) {
        res[i] += kuriagari;
        kuriagari = res[i] / 10;
        res[i] %= 10;
    }

    // 出力
    if (kuriagari) cout << kuriagari;    
    for (auto val : res) cout << val;
    cout << endl;
}