Educational DP Contest / DP まとめコンテスト S - Digit Sum

問題
提出コード

解法

桁DPです。というより、こちらとまったく同じ問題です。

emtubasa.hateblo.jp

ただし、入力の順番だけが異なります。

感想

だいぶ前に通したコードなので、改めて書き直しました。
つい先日のABCでも桁DPが解法になりうる問題が出ていたので、今回はさらっと遷移を書くことができたと思います。
思考の流れとしては、とんでもない大きさの数が与えられているのでまず桁DPを疑います。あとは、桁DPの基本に乗っ取り、未満が確定しているかどうか、を情報として持ちつつ、ある桁でどの数字を選んだらどのようになるか、という遷移を丁寧に考えていけば解くことができます。