概要
AtCoderのABC235のDを解いた。解説に書かれているような実装をしたはずだったのにハマったので、解法のメモ。
※以下、本問に関する解法を含みます。
アプローチ
まず前提となる、この問題を解く上での大まかなアプローチ。
始点が決まっていて、操作の種類も少ない。基本的に定数を乗じるか、数字を文字列とみなしてローテーションするだけなので桁が減ることもない。
1から始めて$N$までの最短路をグラフ上で探索するような問題になりそう。
ただ、増やす方向には無限にいくらでも操作できてしまうし、桁のローテーションにより桁数が減ることがなくても数字としては小さくなる場合があるので、探索中に得られた数字が探している$N$よりも大きくなったからといって探索を止めるわけにはいかない。なので、探索範囲が無限大になってしまう可能性があるように見える。1
そこで、各操作を行う前の状態を復元することも容易であることに注目し、求めたい$N$から逆に辿って、1に行きつくまでの最短回数を求めることにする。これであれば、桁数は広義単調減少なので、いずれは1にいきつくか途中で息詰まるので、気持ちとしても安心。
この方法は、実は解説の末尾でも提示されている。
実装のハマりどころ
$a$を掛ける操作に対応する、$a$で割る操作については特に注意点はない。あらかじめ割り切れるかどうか確認してから割ってやるくらい。
問題は、末尾の桁を先頭に持ってくる右シフト的な操作である。
基本的には、数字が1桁ならシフトはしない、2桁以上であれば逆に左シフトしてあげる、でよい。
但し、左シフト後に0から始まるような数値になってしまう場合は、そのような復元はできないことに注意しなければならない。
例えば、706543を左シフトすると065437になる。しかしこれは整数として見ると65437であるから、右シフトしたら76543になるのであり706543にはならない。
このことに気を付けないと、正解よりも少ない回数で遷移できると判断してしまったり、本来は遷移できないのに遷移できると判断してしまう。
提出したコード
最短経路を求める問題に帰着できるということには解説を読んでから気づいたので、深さ優先探索してて恥ずかしい。
上記のミスに気づいておらずWA
上記のミスに気付いてACしたもの