【AtCoder】ABC 444 D - Many Repunit Sum

2026-02-09

AtCoder/ABC/D問題 AtCoder/ABC/400点問題 AtCoder/茶Diff AtCoder/NoviSteps/未分類 AtCoder/数学/桁ごとに考える AtCoder/数学/レピュニット数 AtCoder/imos法競技プログラミング

D - Many Repunit Sum

D - Many Repunit Sum

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 574 / NoviSteps: ??? / 配点: 400 点

問題概要

$i=1,2,\dots,N$ に対して、 $1$ を $A_i$ 個つなげた整数を $B_i$ と表す。 $\sum_{i=1}^{N}{B_i}$ を求めよ。

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 2 \times 10^5$
入力される値は全て整数

考察

テストケース2にもあるように、 $B_i$ の桁数は最大で $2 \times 10^5$ 桁となり、多倍長整数をもってしても計算量が怪しい。

したがって、足し算の筆算の要領で、下の位から桁ごとに縦に足し合わせていくことを考える。

$B_i$ は $0$ 桁目から $A_i - 1$ 桁目までが $1$ である数だから、これらの総和を取ったとき、 $d$ 桁目に現れる $1$ の個数 $c_i$ ( $d$ 桁目の数)は、 $A_i > d$ であるような $i$ の個数に等しい。

これは、imos法で $0$ 桁目を $+1$ 、 $A_i$ 桁目を $-1$ として差分管理し、累積和を取ることによって効率的に求められる。

また、 $c_i > 9$ のときは上位の桁への繰り上がりが発生する。これは、

$c_{i+1} = \left\lfloor \dfrac{c_i}{10} \right\rfloor$
$c_i \leftarrow c_i \mod 10$

のように更新すればよい。

詳しくは実装例を参照のこと。

実装例

39~42行目の処理は、30~37行目のループでiをMAX - 1まで回すことによって生じる上位桁の $0$ を削除するためのものである。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define all(x) (x).begin(), (x).end()
5.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
6. 
7.using ll = long long;
8. 
9.// ======================================== //
10. 
11.int main()
12.{
13.    int N;
14.    cin >> N;
15.    vector<int> A(N);
16.    rep(i, 0, N) cin >> A[i];
17. 
18.    const int MAX = 200200;
19. 
20.    vector<int> imos(MAX, 0);
21.    rep(i, 0, N)
22.    {
23.        imos[0]++;
24.        imos[A[i]]--;
25.    }
26. 
27.    vector<int> ans;
28.    ll ps = 0;
29.    ll carry_out = 0;
30.    rep(i, 0, MAX)
31.    {
32.        ps += imos[i];
33. 
34.        ll sum = ps + carry_out;
35.        ans.push_back(sum % 10);
36.        carry_out = sum / 10;
37.    }
38. 
39.    while (!ans.empty() && ans.back() == 0)
40.    {
41.        ans.pop_back();
42.    }
43. 
44.    reverse(all(ans));
45.    for (auto &&d : ans)
46.    {
47.        cout << d;
48.    }
49.    cout << endl;
50. 
51.    return 0;
52.}

https://atcoder.jp/contests/abc444/submissions/73081839

実装時間: 20分

コメント

ゾロ目回ってレピュニット数関連の問題出がちだよね。