精進 ABC077D-Small Multiple
すごくいい経験になったと思う
これからも使いそうな考え方を書いておく
この問題の特徴
まず、目に付くのは
「Kの正の倍数」という制限
僕は、このような「上に無制限」な問題に慣れていなかったのがダメだった思う
じゃあどうするの
なんとかして、この「Kの正の倍数」という無制限さを
有限に置き換えたい
どうするか
Kの倍数ということは
すべてKで割った時の剰余が0になる
まずこれに目をつけなければならなかった
また、数同士の関係性についても考えてみる
1 -> 2
1を足すと桁の和が1増える
1 -> 10
10を掛けると桁の数は変わらない
これを mod K の有限の世界で考えると
K の倍数、つまり 0 (mod K)を目指せばいいということだ
これは 0~K-1について
上の関係性のグラフを貼れば求めることができる(これは01BFS)
世界を狭める方法を考えることが大事だった
このような経験がなかったので成長できたと思う
