ABC 379
Table of Contents
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$ の位の寄与とすると、各位の寄与は次のように表せる。
- 1の位の寄与: $X_0 = \sum_{i=1}^N i \times S_i$.
- 10の位の寄与: $X_1 = (X_0 - S_N \times N) \times 10$.
- 100の位の寄与: $X_2 = \left\{ X_1 - 10 S_{N-1} \times (N-1) \right\} \times 10$
と表せる。
一般に $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