この解説では 公式解説 の理解を前提としています．

このユーザー解説は，公式解説と別の解法を説明するものではありません．

公式解説の dp は，「これから下位桁から生じると仮定する，繰り上がりの量」を状態に組み込むものです．この発想を，下位桁から決める dp からも導けるということについて解説します．

---

[1] 下位桁から決める dp

本問で答えをひとつだけ求める場合，つまり \(k=N\) についてのみ答えを求める場合には，下位桁から決める dp による解法を考える人も多いと思います．

つまり，\(i=N,N-1,\ldots,2,1\) の順に処理していき，

• その時点での上位桁 \(9\) 桁程度を状態とし，
• 既に確定している下位桁部分の桁和の最小値を値とする

という dp です．この dp では，各 \(i\) ごとに \(2^9\times 2\) 個程度の状態を持ちます．この状態数は

• 最後に処理した \(9\) 個の \(i\) に対する選択に加えて，
• 下位桁から生じている繰り上がりの量（\(0\) または \(1\)）

によるものです．

\(k=N\) に対する値だけを求めるならば，この方法で解くことができます．しかし本問題ではすべての \(k\) での値の出力を要求されていて，この方法で解くことは難しいです．

---

[2] dp の向きの変換

このような下位桁から決める桁 dp は通常，ある程度機械的に，上位桁から決める桁 dp へと変換することが可能です．

上で解説した dp は，ある DAG における \(s\to t\) 最短路長を求めていると解釈することができます．DAG の頂点は dp の状態全体で，上の解説の手法だと \(N\times 2^9\times 2\) 程度です．dp 遷移が状態間の重み付き有向辺に対応します．dp での値は，各状態について，「\(s\) からの最短路長」を求めることに対応します．

一方で，DAG における \(s\to t\) 最短路長を求める問題は，逆順に解くこともできます．つまり，各状態について「\(t\) までの最短路長」を表す dp テーブルを考えて，これを \(t\) 側から順に求めていくことができます．

このようにして，下位桁から決める桁 dp を，上位桁から決める桁 dp に変換することができます．転置原理 を知っている方は，その変種と解釈してもよいでしょう．

本問ではすべての \(k\) での答を求めるという都合上，本解説冒頭で述べた解法をそのまま上位桁から決める桁 dp に変換しても，公式解説で扱った解法そのものが直ちに得られるわけではありません．ただし公式解説の解法の考え方に類似した，非常に近い状態設計の dp に至ることが可能です．

---

[3] 上位桁から決める dp における繰り上がり

下位桁から決める桁 dp では，典型的には，状態設計に

• これまで下位桁で生じた，繰り上がりの量

を組み込むことになります．このような桁 dp を上位桁から決める桁 dp に変換すると，状態設計に

• これから下位桁から生じると仮定する，繰り上がりの量

を組み込むことになります．

これは自然な対応ではありますが，前者の

• これまでに起こることが確定した事象を状態に組み込む

ことに比べて，後者の

• まだ確定していない将来の事象を仮定して状態に組み込む

ことは，より発想の難易度が高くなります．本問題の難しさはこの点にあると言えるでしょう．