考察
末尾を削った数を一つずつ作って加える代わりに、右揃えの筆算で同じ位へ入る数字をまとめる。その合計は元の数の接頭辞の桁和になるため、桁和を一つずつ減らしながら、下の位から答えを確定できる。
入力を十進表記の文字列として受け取り、その桁数を とする。最大50万桁なので、通常の整数型には収まらない。また、 なら となるため、非零の項は の 個だけである。ただし、この全項を作って巨大整数として足すと、扱う桁数の合計が となってしまう。
右揃えの同じ列にはどの桁が入るか
なら、求める和は である。右揃えにして書くと、各位に何が足されるかが分かる。
123
12
+ 1
-----
136
一の位には 、十の位には 、百の位には1が入る。元の数を項ごとに処理する代わりに、この列ごとの合計を求めればよい。
一般に、元の数の左から 桁目の値を (1始まり)とする。 では末尾の 桁が削られるので、残った の位は である。指数 を固定すると、対応する項は に一意に決まる。 を満たす位置は なので、 の位にはその範囲の数字がちょうど1回ずつ入る。
そこで、接頭辞の桁和を と定義すると、答えは
となる。123の例なら で、 である。一般には係数が10以上になるので、繰り上がりも処理する。
桁和を減らす順序と繰り上がり
最初は全桁和 を sum に入れ、繰り上がり carry を0にする。 の順に、次を行う。
carry に sum を加える。
carry を10で割った余りを、答えの次の一桁としてバッファへ追加する。
carry を10で割った商へ更新する。
sum から を引く。
処理前の sum は現在の列に必要な であり、次の列で必要なのは である。現在の列を処理してから右端の数字を引くのはこのためだ。123なら、6を使った後に3を引いて次の列の3を得て、3を使った後に2を引いて次の列の1を得る。先に引くと、今の列へ入るはずの数字を落としてしまう。
全入力桁を使った後も、carry が残る間は余りを追加して10で割る。例えば では、一の位は から8で繰り上がり1、十の位は から0で繰り上がり1となる。最後の1も追加して、反転すれば が得られる。
典型の発動条件
巨大整数の桁別集約
非常に長い整数の桁をずらした項の和など、同じ出力桁への寄与をまとめやすいときに使える。まず小さい入力を右揃えで書き、列ごとの合計が接頭辞和などで更新できないかを探す。
各列の合計と繰り上がりが通常の整数型に収まれば、巨大整数の加算を繰り返すことなく、商と余りだけで正確な十進表記を構成できる。
問題固有の要素
上限 まで反復する必要はない。末尾を削り続ければ 回で0になることが、和の実効的な打ち切り位置を与える。
別の問題へ持ち帰る視点: 和の添字上限が巨大なときは、入力のサイズだけで各項が恒等的に0になる位置を決められないかを調べる。
正当性
の項は0である。残る各項の各桁について、位置 の数字が の位へ入るのは の項だけである。従って、その列に入る数字を漏れも重複もなく足すと になる。
各反復の開始時には sum が 、carry が下位の列からの繰り上がりを表す。初回は なので全桁和でよく、反復の最後に を引くことで、次回の sum は となる。
現在列の合計を とすると、 である。余りをその位の数字として確定し、商を上へ送れば値を保てる。この操作を全列と残った繰り上がりに施し、得た数字列を反転するので、求める和を正しく出力できる。
実装上の注意
- 数字を文字から整数へ変換して全桁和を作る。現在の列への加算、余りの出力、繰り上がりの更新を済ませた後で、処理した右端桁を桁和から引く。
- 入力中に0があっても手順は同じである。例えば の一の位は1になり、次の桁和は0を引いて1のままとなる。最終結果は である。
- 全入力桁を処理してから、残った
carry を出し切る。0になった後には余分な桁を追加しない。逆順に蓄えた数字列を最後に一度だけ反転する。
- なら和は そのものである。入力は正なので答えも正となり、上記手順で先頭に不要な0は生じない。
復習の核
- 桁をずらした多数の整数の和は、まず右揃えの筆算を書く。「同じ出力桁へどの入力桁が入るか」を調べると、巨大整数の加算を列ごとの集計へ変えられる。
- 本問は各入力桁が同じ列へ1回ずつ入るので通常の接頭辞桁和になる。ABC379 Eでは部分文字列の左端の選び方による重みが付く。寄与の回数は問題ごとに数え、係数を下位から繰り上げる手順を共通化する。
- 接頭辞和を短くするのは、現在の列を処理した後である。更新の前後で、保持する量がどの範囲を表すかを言葉にする。
計算量と制約
時間
。全桁和の計算、 列の処理、出力バッファの反転と出力はいずれも線形時間である。桁和は高々 、繰り上がりは高々 に保たれるため、残った繰り上がりの処理は高々 桁で済む。
空間
。入力文字列と答えのバッファを保持する。桁和は一つの変数で更新でき、接頭辞和の配列は不要である。
制約との対応
より である。桁和は高々450万、下位からの繰り上がりとの和も高々 なので、列ごとの演算は32 bit整数に収まる。答え全体を整数型へ格納せず、文字列として線形時間で構成する。
公式問題文・個別公式解説を2026-10-21に再照合した。
出典