ARC084 D: Small Multiple

arc084.contest.atcoder.jp

解き方

  • +1*10の2つの計算を辺、自然数を頂点としてグラフを作る
    • 自然数全体を頂点にはできないのでmod Kする
    • コストは各桁の和の変化量(それぞれ1, 0)
  • 01BFSで1 mod Kから0 mod Kまでの最短距離を求める

ハマったところ

  • 自然数の関係をグラフに落とし込む発想ができなかった
  • 01BFSを知らなかった
    • そろそろutil拡充(グラフ関連)をしたい

github.com