ABC288F - Integer Division、数式少なめの解法
問題
解説
数式の変形に頼らずなるだけ直観的に解く方法について、例を用いて解説します。
例えば $ X = 2345 の 3 文字目まで見終わったとき、その時点での $ f(S) の総和は
$ 234 + 2 \times 34 + 23 \times 4 + 2 \times 3 \times 4
ですが、これを
$ 1 個の $ 234
$ 2 個の $ 34
$ 23 個の $ 4
$ (2 \times 3) 個の $ 4
の和と解釈し、個数の総和 $ c\lbrack 3 \rbrack と $ f(S) の総和 $ s\lbrack 3 \rbrack のみを記録しておきます。
4 文字目まで見たときの個数の総和 $ c\lbrack 4 \rbrack と $ f(S) の総和 $ s\lbrack 4 \rbrack は次のように求められます。
5 を単独で用いる場合 : $ 5 が $ s\lbrack 3 \rbrack 個増えるので、$ c\lbrack 4 \rbrack への寄与は $ s\lbrack 3 \rbrack、$ s\lbrack 4 \rbrack への寄与は $ 5 s\lbrack 3 \rbrack となります。
5 を繋げて用いる場合 : いままでの数全てが $ 10 倍された上 $ 5 を足されるので、$ c\lbrack 4 \rbrack への寄与は $ c\lbrack 3 \rbrack、$ s\lbrack 4 \rbrack への寄与は $ 10 s\lbrack 3 \rbrack + 5 c\lbrack 3 \rbrack となります。
具体的な遷移はこれらを合わせた
$ c\lbrack 4 \rbrack = s\lbrack 3 \rbrack + c\lbrack 3 \rbrack
$ s\lbrack 4 \rbrack = 5 s\lbrack 3 \rbrack + (10 s\lbrack 3 \rbrack + 5 c\lbrack 3 \rbrack)
となります。
1 個の 0 がある状態（$ c\lbrack 0 \rbrack = 1, s\lbrack 0 \rbrack = 0）を初期状態として同様の遷移を繰り返すことで $ O(N) で答えが求まります。
提出
元ポスト