コンテスト中の考察 前から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)にできる 問題: