[0] 記号などの定義

• \(A_i\) の桁数の最大値を \(K\) とします。
• 数字の種類数 (位取り記数法の基数) を \(B\) とします。
• 文字列 \(S\) の \(i\) 文字目を \(S[i]\)、区間 \([i,j )\) の部分文字列を \(S[i,j)\) とします。
• \(x\) は Leading Zero を適切に加えることで、長さ \(K\) の文字列として扱います。(添字の順序が反転することに注意)
• \(0 \leq i < B^N\) なる整数 \(i\) に対し、\(i\) を長さ \(N\) の文字列としたとき、その文字列を反転させた文字列が表わす数を \(\mathrm{rev}(i,N)\) とします。
• 数と文字列を暗黙に変換している部分がありますが、いい感じに解釈してください。

---

[1] 条件の言いかえ

\(\sum_{i=1}^N f(A_i)\) は定数なので、\(\sum_{i=1}^N \{f(A_i+x)-f(A_i)\}=\sum_{i=1}^Nf(x)+\sum_{i=1}^N\{f(A_i+x)-f(A_i)-f(x)\}\) の最小値を求めるとしてよいです。

\(\sum_{i=1}^N f(x)\) の寄与は以下のように言いかえられます。

• \(0 \leq j \leq K, 1 \leq k < B\) に対し、\(x[j]=k\) であった場合、\(Nk\) の寄与が生じる。

\(f(A_i+x)-f(A_i)-f(x)\) は、\(A_i\) と \(x\) の和を筆算で計算するときの繰り上がりの回数を \(-(B-1)\) 倍したものに等しいです。桁ごとに分解して考えます。\(B^{K-1-j}\) の位から \(B^{K-j}\) の位への繰り上がりが発生する条件は、\(A_i \bmod B^{K-j} + x \bmod B^{K-j} \geq B^{K-j}\) つまり \(x \bmod B^{K-j} \geq B^{K-j} - A_i \bmod B^{K-j}\) となります。

\(x \bmod B^{K-j}\) と \(B^{K-j} - A_i \bmod B^{K-j}\) を長さ \(K-j\) の文字列と考えたときの最長共通接頭辞の長さで場合分けすることで、以下のように言いかえられます。

• \(0 \leq j < K, j < k \leq K\) に対し、\(B^{k-j}-A_i[j,k) \leq x[j,k) < B^{k-j}-BA_i[j,k-1)+B\) であった場合、\(-(B-1)\) の寄与が生じる。

例えば、\(B=10, K=3, A_i=123\) のときの考える必要のある寄与は以下のようになります。

• \(9 \leq x[0,1) < 10\) であった場合、\(-9\) の寄与が生じる。
• \(88 \leq x[0,2) < 90\) であった場合、\(-9\) の寄与が生じる。
• \(877 \leq x[0,3) < 880\) であった場合、\(-9\) の寄与が生じる。
• \(8 \leq x[1,2) < 10\) であった場合、\(-9\) の寄与が生じる。
• \(77 \leq x[1,3) < 80\) であった場合、\(-9\) の寄与が生じる。
• \(7 \leq x[2,3) < 10\) であった場合、\(-9\) の寄与が生じる。

考える必要のある寄与は合計で \(O(BK+NK^2)\) 個となります。

---

[2] 分割統治

\(x\) としてありうる \(B^K\) 通りすべてについて答えを計算することを考えます。

分割統治を行います。以下のものが計算できたとします。ただし、\(m=\lfloor\frac{K}{2}\rfloor\) とします。

• \(0 \leq a < B^m\) それぞれについて、\(x[0,m)=a\) のときの区間 \([0,m)\) に含まれる寄与の総和 \(\text{left}[a]\)
• \(0 \leq b < B^{K-m}\) それぞれについて、\(x[m,K)=b\) のときの区間 \([m,K)\) に含まれる寄与の総和 \(\text{right}[b]\)

\(m\) を通る寄与のみ考えればよいです。\(0 \leq i < m, m<j \leq K\) なる \((i,j)\) について、区間 \([i,j)\) に以下のような寄与があるとします。

• \(l \leq x[i,j) < r\) の場合、\(w\) の寄与が生じる。

ただし、区間 \([l,r)\) に属する整数はすべて \(1\) の位以外が一致していることが、[1] の考察内容からわかります。このとき、\(x[0,m)=a, x[m,K)=b\) としたとき、

\[ \begin{aligned} & \phantom{\iff} l \leq x[i,j) < r \\ & \iff a[i,m)=l[0,m-i) \land l[m-i,j-i) \leq b[0,j-m) < l[m-i,j-i)+(r-l) \\ & \iff \mathrm{rev}(l[0,m-i),m) \leq \mathrm{rev}(a,m) < \mathrm{rev}(l[0,m-i),m)+B^i \\ & \phantom{\iff} \land \, l[m-i,j-i) \cdot B^{K-j} \leq b < \{l[m-i,j-i)+(r-l)\}\cdot B^{K-j} \end{aligned} \]

となり、\(x\) 軸に \(\mathrm{rev}(a,m)\)、\(y\) 軸に \(b\) を割り当てたときの \(B^m \times B^{K-m}\) のグリッド上の長方形に対応します。この長方形に含まれるマスに \(w\) を加えるためには、\(2\) 次元 imos 法を用いればよいです。

---

[3] データ構造による高速化

[2] の解法の計算量は \(\Omega(B^K)\) となり、AC することができません。\(B^K\) 通りの \(x\) すべてについて答えを計算していますが、最後のステップで必要なのはそれらの最小値であることを利用して高速化を行います。

上と同様に、長方形に含まれるマスへの加算に言い換えます。最終的に以下のような問題に帰着されます。

\(H \times W \ (H=B^m, W=B^{K-m})\) のグリッドがあり、最初は各マスに \(0\) と書かれている。長方形を指定し、その長方形に含まれるマスそれぞれにある数を加算することを \(Q=O(BK+NK^2)\) 回行う。\(Q\) 回の操作後に、マスに書かれている数の最小値を答える。

これは、区間加算・区間最小値の遅延セグメント木を管理しながら平面走査を行うことで、\(O(H+W+Q\log W)\) 時間で解くことができます。

最終的な時間計算量は \(O(B^\frac{K}{2}+(NK^3+BK^2)\log B)\) となります。

実装例: https://atcoder.jp/contests/arc153/submissions/38023362