ABC 379

https://atcoder.jp/contests/abc379

A. Cyclic

https://atcoder.jp/contests/abc379/tasks/abc379_a

B. Strawberries

https://atcoder.jp/contests/abc379/tasks/abc379_b

C. Sowing Stones

https://atcoder.jp/contests/abc379/tasks/abc379_c

D. Home Garden

https://atcoder.jp/contests/abc379/tasks/abc379_d

E. Sum of All Substrings

https://atcoder.jp/contests/abc379/tasks/abc379_e

自力 AC.

サンプル 1 の 379 について考えてみる。

\begin{align*} &3 + 37 + 379 + 7 + 79 + 9 \\ &= 3 + 7 + 7 + 9 + 9 + 9 + 30 + 70 + 70 + 300 \end{align*}

各位の寄与ごとに分解して考えてみる。

1 の位の寄与

3
7 7
9 9 9

10 の位の寄与

30
70 70

100 の位の寄与

300

これより以下のような数列が成り立つことを推測した。

$X_i$ を $10^i$ の位の寄与とすると、各位の寄与は次のように表せる。

と表せる。

一般に $10^k$ の位の寄与 $X_k$ は $X_k = \left\{ X_{k-1} - 10^{k-1} S_{N-(k-1)} \times (N-(k-1)) \right\} \times 10$

この値を 1 の位から順に求め、最後に繰り上がり分を考慮して最終的な答えとする。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    string S;
    cin >> N >> S;

    reverse(all(S));

    ll sum = 0;
    rep(i, N) {
        ll x = S[i] - '0';
        sum += x * (N - i);
    }

    // 桁数は最大で N+1
    vll ans(N + 1);
    rep(i, N) {
        ans[i] = sum;
        ll x = S[i] - '0';
        sum -= x * (N - i);
    }

    rep(i, N) {
        ll q = ans[i] / 10;
        ans[i + 1] += q;
        ans[i] %= 10;
    }
    if (ans.back() == 0) ans.pop_back();

    reverse(all(ans));
    for (ll x : ans) cout << x;
    cout << endl;
}

F. Buildings 2

https://atcoder.jp/contests/abc379/tasks/abc379_f

G. Count Grid 3-coloring

https://atcoder.jp/contests/abc379/tasks/abc379_g