ヒント → https://atcoder.jp/contests/arc153/editorial/5482

\(A\) を非負整数列とするとき，\(\sum_{i=1}^N f(A_i+x)\) としてありうる最小値を \(F(A)\) と書くことにします．

また，\(A_i\) の桁数の最大値を \(K\) とします．

[1] \(F(A)\) の再帰的な計算

\(0\leq r\leq 9\) に対して，\(x\) を\(x\equiv r \pmod{10}\) であるものに限定したときの最小値を \(F_r(A)\) と書くことにします．\(F(A) = \min_{r} F_r(A)\) です．

例えば \(r=1\) の場合，\(x=10x'+1\) とすると，\(f(123+x)=f(12+x')+4\), \(f(45+x)=f(4+x')+6\) などにより，

\[F_1((123,45,678,90)) = 20 + F((12,4,67,9))\]

となります．同様に \(r=5\) とすると

\[F_5((123,45,678,90)) = 16 + F((12,5,68,9))\]

となります．このようにすると，\(\max(A)\geq 2\) のときには \(F(A)\) をより値の小さな数列 \(A'\) に対する \(F(A')\) から計算できます．\(\max(A) = 1\) のときには明らかに \(F(A) = \text{sum}(A)\) なので，この方法で \(F(A)\) を計算することができます．

[2] 状態数の評価

[1] の方法で再帰的に \(F(A)\) を計算するとき，\(F(A')\) の計算が必要となる \(A'\) としてどのくらいの場合があるかを考えます．

計算手順を考えれば，深さ \(k\) の再帰で呼ばれる \(A'\) は，ある \(0\leq c < 10^k\) に対して \(A'_i = \biggl\lfloor \dfrac{A_i + c}{10^k}\biggr\rfloor\) と書けるものに限られることがわかります．

したがって，\(i=1,2,\ldots,N\) を \(A_i\bmod 10^k\) が昇順となるように並べ替えたものを \(i_1, i_2, \ldots, i_N\) とすれば，計算対象となる \(A'\) は次の形のものに限られます：

\[A'_i = \begin{cases}\biggl\lfloor \dfrac{A_i}{10^k}\biggr\rfloor & (i = i_1, \ldots, i_n) \\ \biggl\lfloor \dfrac{A_i}{10^k}\biggr\rfloor+1 & (i = i_{n+1}, \ldots, i_N)\end{cases}\]

このようにして定まる数列 \(A'\) を \(A(k, n)\) と書くことにします．このような数列は高々 \(K(N+1)\) 通りであることが分かります．

[3] まとめ

以上により，本問は \(\text{dp}[k][n] = F(A(k,n))\) （\(0\leq k < K, 0\leq n\leq N\)）によって定まる \(\text{dp}[k][n]\) を \(k\) について降順に計算していく動的計画法により解くことができます．各 \(k\) に対して \(A_i\bmod 10^k\) をソートする部分がボトルネックとなり，全体の計算量は \(O(NK\log N)\) となります．なお，基数ソートの要領で，\(A_i\bmod 10^k\) のソートに，\(A_i\bmod 10^{k-1}\) のソート結果を利用することで，計算量を \(O(NK)\) とすることも可能です．

すべての数列 \(A(k,n)\) に対して、数列のすべての項を直接調べるような \(\Omega(N)\) 時間の計算を行ってしまうと計算量が悪化してしまうことに注意してください．[1] で述べたような計算式を得るために必要になるのは \(A(k,n)\) の \(1\) の位の度数分布だけなので， \(A(k,n+1)\) の場合と \(A(k,n)\) の場合の差分などに注目したり，適当な累積和を利用することで計算を高速化できます．