考察
全部分文字列を数に直して足す代わりに、筆算の同じ位へ入る数字をまとめる。元の各桁がその位に何回現れるかを数えれば、部分文字列の列挙を消せる。あとは通常の筆算と同じく、下の位から繰り上がりを処理すればよい。
部分文字列は 個あり、一つずつ取り出すだけでも かかる。さらに答えも長い整数になるので、巨大整数への加算を繰り返す方針は避けたい。そこで、和を構成する一つの桁へ注目する。
元の桁位置と、部分文字列での位を分ける
元の文字列を左から1始まりで番号付けし、位置 の数字の値を とする。部分文字列の左端を 、右端を とすると、その中の は右から 桁だけ離れている。従って、この桁が部分文字列の値に加える量は である。
ここで を固定する。 を含み右端が である部分文字列の左端は の 通りなので、これらを合わせた寄与は
となる。この段階では、同じ右端でも元の桁位置ごとに10の指数が異なる。
次は筆算の列、つまり10の指数を固定したい。指数を と置くと、 の位へ寄与できる元の位置は であり、右端は に一意に決まる。よって、その位へ入る数字の合計は
である。重み付きの接頭辞和を と定義すれば、求める答えは
と書ける。ここで は接頭辞和の範囲を表す添字である。 は、右端を に固定した部分文字列の値の和ではなく、同じ位へ集めた、繰り上がり前の係数である。
123の筆算から係数と繰り上がりを確かめる
の全6部分文字列は で、和は164になる。右揃えの筆算にすると、各列の数字の合計が見える。
1
12
123
2
23
+ 3
-----
164
百の位には1が1回、十の位には1が1回と2が2回、一の位には1が1回、2が2回、3が3回入る。従って 、、 であり、上の和は となる。係数14は一桁に収まらないので、下の位から次のように処理する。
- 一の位: 係数14から4を確定し、1を十の位へ送る。
- 十の位: 係数5に繰り上がり1を足した6を確定する。次への繰り上がりは0。
- 百の位: 係数1をそのまま確定する。繰り上がりも残らず、答えは164となる。
右端を固定した和との違いも確かめておこう。右端が3の部分文字列の和は であり、 とは異なる。
係数を作り、下の位から答えを確定する
まず とし、左から を計算する。次に繰り上がり carry を0で始め、 の順に次を行う。
carry に を加える。
carry を10で割った余りを、答えの次の一桁として出力用バッファへ追加する。
carry を10で割った商へ更新する。
全係数を使っても carry が残っていれば、余りの追加と商への更新を0になるまで続ける。例えば では係数が で、一の位は7で繰り上がり2、十の位は から1で繰り上がり1となる。この最後の1も出力して、 を得る。最後にバッファを反転すれば答えになる。
典型の発動条件
巨大整数の桁別寄与と筆算
答えが長い整数で、多数の項をそのまま足すのが重いときに候補となる。各項を「数字の値×基数の冪」へ分解し、同じ冪へ入る寄与を効率よく数えられるかを調べる。
得られた係数が基数以上でもよい。係数と下位からの繰り上がりの和を商と余りに分ければ、答え全体を通常の整数型へ入れずに構成できる。ただし、係数と繰り上がり自体が使用する整数型に収まることは確認する。
問題固有の要素
左端の選択肢が 通りあることが、元の桁 に掛かる重みとなる。一方、 の位を固定すると右端は に決まるため、右端の選択肢の数をさらに掛けることはない。
別の問題へ持ち帰る視点: 同じ元の桁でも、選ぶ区間によって出力上の位が変わる。出現回数だけでまとめず、「どの位へ何回入るか」まで固定して数える。
正当性
各部分文字列の値は、その中の各桁の寄与の和である。位置 の桁と右端 を固定したとき、左端の 通りから合計 が加わる。これにより、すべての部分文字列のすべての桁を漏れも重複もなく数えている。
指数 ごとにこの有限和を集め直すと、 に対する係数は となる。従って答えは である。
筆算では、現在の係数に下位からの繰り上がりを足した値を とすると、 が成り立つ。余りを現在の位に置き、商を次の位へ送っても値は変わらない。下位の確定済みの桁には以後の係数が影響しないため、全係数と残った繰り上がりを処理すれば、上の和の十進表記が得られる。
実装上の注意
- 文字列を0始まりで持つ場合も、位置の重みは「添字+1」にする。
- なので、上限では になる。係数・累積値・
carry には64 bit整数を使い、積もその型で計算する。
- 係数を全て使った後の繰り上がりを忘れない。数字は下位から追加するので、最後に一度だけ反転する。
- 入力は1〜9だけなので答えは正であり、先頭に不要な0は生じない。 でも同じ手順で入力の数字そのものを出力できる。
復習の核
- 区間ごとの値を足すのが重いときは、「元のどの桁が、出力のどの位へ、何回現れるか」を固定する。元の位置・右端・10の指数を別の添字で書くと混乱しにくい。
- ABC233 Eでは各桁が同じ列へ1回ずつ入り、通常の接頭辞桁和になる。本問では左端が 通りあるため重み が付く。係数は数え直し、下位から繰り上げる筆算を再利用する。
計算量と制約
時間
。重み付き接頭辞和を作り、 個の係数を各1回処理する。繰り上がりは の値に収まるので、残りの処理は高々 桁である。出力バッファの反転と出力も含めて線形時間となる。
空間
。入力文字列、係数列、答えのバッファを保持する。
制約との対応
、入力の各数字は1〜9である。全部分文字列の列挙を避け、係数と繰り上がりだけを64 bit整数で扱うことで、答えが通常の整数型に収まらなくても線形時間で出力できる。
公式問題文・個別公式解説を2026-10-21に再照合した。
出典