Toyota Programming Contest 2023 Spring Qual A (AtCoder Beginner Contest 288) F - Integer Division (500)
コンテスト中の考察
前からDPで考えていくと区切り位置毎に遷移元が$ \mathcal{O}(N)あって全体で$ \mathcal{O}(N^2)になってしまう
解説の解法
上の遷移の式を式変形して高速化すると$ dp_i = 10 dp_{i-1} + X_i \sum_{j}^{i-1} dp_jとできる
$ dp_iの累積和を持つことで全体で$ \mathcal{O}(N)にできる