[1] 上位桁と下位桁

\(X_i\) の下位 \(9\) 桁を \(R_i\)，より上位の桁を \(L_i\) としましょう．つまり

\[ L_i = \lfloor X_i / 10^9 \rfloor,\qquad R_i = X_i \bmod 10^9 \]

とします．

これらについて，おおよそ次のことが分かります．

• \(R_i\) は直近の \(9\) 回の選択のみによって定まるため，高々 \(2^9\) 通りである．
• \(L_i\) はこれ以降の計算によってほとんど変わらない．

\(L_i\) がほとんど変わらないというのは，\(10\) 進法表記がそのままの形のまま，上位桁にシフトしていくということです．ただし，下位桁からの繰り上がりによって，将来的に上位桁が \(L_i\) から \(L_i+1\) に変化するということは起こりえます．

[2] dp テーブルの定義

以上を踏まえて，次のような dp テーブル定義を考えます．

各 \(X_i\) まで定めた時点について，次で定まる \(2^9\times 2\) 個の値

\[ \mathrm{dp}[s][x]\qquad (0\leq s < 2^9, 0\leq x \leq 1) \]

を定義します．まず \(s\) は直近 \(9\) 回の選択（\(A_i\) または \(B_i\) のどちらか）を表すこととします．そして \( \mathrm{dp}[s][x]\) は，\(X_i\) の上位桁を \(L_i\) としたときに

• \(L_i+x\) の桁和としてありうる最小値

を表すこととします．

dp テーブルが定義できたら，あとは定義に従って丁寧に遷移式を作ればよいです．dp テーブルから答を読み取ることも容易です．

なおほとんど同じことですが，下位桁を \(R_i\) として \(\mathrm{dp}[R_i][x]\) という値を同様に定義してもよいでしょう．この場合はハッシュマップなどを用いて実装することになり，実行時間は遅くなりますが，十分 AC 可能です．