ABC 233 E — Σ[k=0..10^100]floor(X/10^k)

考察

末尾を削った数を一つずつ作って加える代わりに、右揃えの筆算で同じ位へ入る数字をまとめる。その合計は元の数の接頭辞の桁和になるため、桁和を一つずつ減らしながら、下の位から答えを確定できる。

入力を十進表記の文字列として受け取り、その桁数を LL とする。最大50万桁なので、通常の整数型には収まらない。また、k≥Lk\geq L なら ⌊X/10k⌋=0\lfloor X/10^k\rfloor=0 となるため、非零の項は k=0,1,…,L−1k=0,1,\ldots,L-1 の LL 個だけである。ただし、この全項を作って巨大整数として足すと、扱う桁数の合計が Θ(L2)\Theta(L^2) となってしまう。

右揃えの同じ列にはどの桁が入るか

X=123X=123 なら、求める和は 123+12+1=136123+12+1=136 である。右揃えにして書くと、各位に何が足されるかが分かる。

  123
   12
+   1
-----
  136

一の位には 3+2+1=63+2+1=6、十の位には 2+1=32+1=3、百の位には1が入る。元の数を項ごとに処理する代わりに、この列ごとの合計を求めればよい。

一般に、元の数の左から jj 桁目の値を xjx_j(1始まり)とする。⌊X/10k⌋\lfloor X/10^k\rfloor では末尾の kk 桁が削られるので、残った xjx_j の位は 10L−k−j10^{L-k-j} である。指数 tt を固定すると、対応する項は k=L−j−tk=L-j-t に一意に決まる。k≥0k\geq0 を満たす位置は 1≤j≤L−t1\leq j\leq L-t なので、10t10^t の位にはその範囲の数字がちょうど1回ずつ入る。

そこで、接頭辞の桁和を Bi=∑j=1ixjB_i=\sum_{j=1}^{i}x_j と定義すると、答えは

∑t=0L−1BL−t10t\sum_{t=0}^{L-1}B_{L-t}10^t

となる。123の例なら B=(1,3,6)B=(1,3,6) で、1×100+3×10+6=1361\times100+3\times10+6=136 である。一般には係数が10以上になるので、繰り上がりも処理する。

桁和を減らす順序と繰り上がり

最初は全桁和 BLB_L を sum に入れ、繰り上がり carry を0にする。i=L,L−1,…,1i=L,L-1,\ldots,1 の順に、次を行う。

  1. carry に sum を加える。
  2. carry を10で割った余りを、答えの次の一桁としてバッファへ追加する。
  3. carry を10で割った商へ更新する。
  4. sum から xix_i を引く。

処理前の sum は現在の列に必要な BiB_i であり、次の列で必要なのは Bi−1=Bi−xiB_{i-1}=B_i-x_i である。現在の列を処理してから右端の数字を引くのはこのためだ。123なら、6を使った後に3を引いて次の列の3を得て、3を使った後に2を引いて次の列の1を得る。先に引くと、今の列へ入るはずの数字を落としてしまう。

全入力桁を使った後も、carry が残る間は余りを追加して10で割る。例えば X=99X=99 では、一の位は 1818 から8で繰り上がり1、十の位は 9+1=109+1=10 から0で繰り上がり1となる。最後の1も追加して、反転すれば 99+9=10899+9=108 が得られる。

典型の発動条件

巨大整数の桁別集約

非常に長い整数の桁をずらした項の和など、同じ出力桁への寄与をまとめやすいときに使える。まず小さい入力を右揃えで書き、列ごとの合計が接頭辞和などで更新できないかを探す。

各列の合計と繰り上がりが通常の整数型に収まれば、巨大整数の加算を繰り返すことなく、商と余りだけで正確な十進表記を構成できる。

問題固有の要素

上限 1010010^{100} まで反復する必要はない。末尾を削り続ければ LL 回で0になることが、和の実効的な打ち切り位置を与える。

別の問題へ持ち帰る視点: 和の添字上限が巨大なときは、入力のサイズだけで各項が恒等的に0になる位置を決められないかを調べる。

正当性

k≥Lk\geq L の項は0である。残る各項の各桁について、位置 jj の数字が 10t10^t の位へ入るのは k=L−j−tk=L-j-t の項だけである。従って、その列に入る数字を漏れも重複もなく足すと BL−tB_{L-t} になる。

各反復の開始時には sum が BiB_i、carry が下位の列からの繰り上がりを表す。初回は i=Li=L なので全桁和でよく、反復の最後に xix_i を引くことで、次回の sum は Bi−1B_{i-1} となる。

現在列の合計を vv とすると、v=(v mod 10)+10⌊v/10⌋v=(v\bmod10)+10\lfloor v/10\rfloor である。余りをその位の数字として確定し、商を上へ送れば値を保てる。この操作を全列と残った繰り上がりに施し、得た数字列を反転するので、求める和を正しく出力できる。

実装上の注意

  • 数字を文字から整数へ変換して全桁和を作る。現在の列への加算、余りの出力、繰り上がりの更新を済ませた後で、処理した右端桁を桁和から引く。
  • 入力中に0があっても手順は同じである。例えば X=10X=10 の一の位は1になり、次の桁和は0を引いて1のままとなる。最終結果は 10+1=1110+1=11 である。
  • 全入力桁を処理してから、残った carry を出し切る。0になった後には余分な桁を追加しない。逆順に蓄えた数字列を最後に一度だけ反転する。
  • L=1L=1 なら和は XX そのものである。入力は正なので答えも正となり、上記手順で先頭に不要な0は生じない。

復習の核

  • 桁をずらした多数の整数の和は、まず右揃えの筆算を書く。「同じ出力桁へどの入力桁が入るか」を調べると、巨大整数の加算を列ごとの集計へ変えられる。
  • 本問は各入力桁が同じ列へ1回ずつ入るので通常の接頭辞桁和になる。ABC379 Eでは部分文字列の左端の選び方による重みが付く。寄与の回数は問題ごとに数え、係数を下位から繰り上げる手順を共通化する。
  • 接頭辞和を短くするのは、現在の列を処理した後である。更新の前後で、保持する量がどの範囲を表すかを言葉にする。

計算量と制約

時間

O(L)O(L)。全桁和の計算、LL 列の処理、出力バッファの反転と出力はいずれも線形時間である。桁和は高々 9L9L、繰り上がりは高々 LL に保たれるため、残った繰り上がりの処理は高々 O(log⁡(L+1))O(\log(L+1)) 桁で済む。

空間

O(L)O(L)。入力文字列と答えのバッファを保持する。桁和は一つの変数で更新でき、接頭辞和の配列は不要である。

制約との対応

1≤X<105000001\leq X<10^{500000} より L≤500000L\leq500000 である。桁和は高々450万、下位からの繰り上がりとの和も高々 10L≤500000010L\leq5000000 なので、列ごとの演算は32 bit整数に収まる。答え全体を整数型へ格納せず、文字列として線形時間で構成する。

公式問題文・個別公式解説を2026-10-21に再照合した。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Σ[k=0..10^100]floor(X/10^k) の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 局所寄与へ分解して集計順を交換する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 寄与の数え上げと順序交換

      執筆: abc-explanation-author1.1.1 / revision 3

      学習の位置

      体系上の位置: 局所寄与へ分解して集計順を交換する

      • 数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。

      この解説で扱わないこと:

      • active集合を時刻・座標順に更新するevent sweep、更新列を逆から読むだけの処理、および成分ごとの解を単に掛け合わせる構造判定。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題