[CodeIQ] 平成変換問題解きました(CodeIQ×はてな エンジニア夏祭り2013)
解き方
解説を見てもやっぱり基本は総当りのようです。
ただし、それだとあまりにもパターン数が増えすぎてしまうので工夫が必要です。
工夫
僕のやった工夫は
- 桁数制限
名前のとおりです。桁数が大きくなりすぎると計算が大変になるのでそれらはあきらめます（速度優先）。ただし、あまり厳しくしすぎないこと。
- 似たものを切り捨てる
例えば
A->B->C->Z
A->B->D->Z
A->B->E->F->Z
とあったとして下の2つは切り捨てました。最短経路という意味では上の2つは最短経路となり得ますが、全部列挙する必要もないため、そうしてます。
- 双方向
これは実際にはやってませんが検討はしました。
さらに
今回
[2]014->[4]014->[16014]->(256)4(4)(81)(9)[6]->1(64)[2]93(36)->(1849)(36)->(4)(36)->26
という答えを見つけましたが、よく見るとこれには無駄な箇所が含まれていました。
256448196から184936に移るところで
(256)4(4)(81)(9)[6]->1(64)[2]93(36)->184936
こうしてるところを
(256)44(81)(9)[6]->1(64)493(36)->184936
こう出来ます
この辺も上の「似たものを切り捨てる」のところでステップ数だけでなく「平方根の回数+２乗の回数」も比較して切捨てていれば解決できたのかなと思います。
面白い問題でした。
追記
解説記事が出てました
https://codeiq.jp/magazine/2013/10/404/
最短7ステップ到達者に名前(kamegu)が載ってました
