問題

正整数 K が与えられる。K の倍数の集合の中で桁和が最小になるとき、その桁和を求めよ。

考え方

任意の正整数は 1 からはじめて、

操作

ある数 t に +1 する
ある数 t に × 10 する

を繰り返し適応することで求められる。上記の操作をするとき +1 するときのみ桁和が +1 される。

K の倍数の集合は mod K でみたときに 0 になる数である。数を同一視するために mod K で考える。

1 からはじめて上記操作によって 0 (mod K) に遷移するときの最小のコストが求める解である。これは K 頂点のそれぞれから、コスト +1 で +1 の頂点に遷移する辺とコスト 0 で *10 (mod K) の頂点に遷移するグラフを考えると、頂点 1 から頂点 0 への最短経路を求めることと同一である。よってダイクストラ法で O(KlogK) で求めることができた。

Submission #3266978 - AtCoder Beginner Contest 077