ange1のブログスマートフォン用の表示で見るange1のブログこの広告は、90日以上更新していないブログに表示しています。数学はじめにCodeIQというところでプログラミング問題「プライム・ホッパー」に解答しましたので、ネタバレです。場合は、次の変換による5回が最小となります。5→53→3→37→7→67解説q以下の素数をノードと見て、ある素数からある素数への変換が可能な場合、辺がつながってると見做すことができ、無向グラフの重み無し最短経路問題として考えることができます。例であれば、67以下の素数の状況を図示すると次のようになります。)そのため、まず各素数に対して、変換可能な素数を辺の情報として挙げてしまい、後はBFSで探索します。最初にq以下の素数を全部調べてしまうため、ムダが多いと言えばそうなのですが、数を付け足す方を調べるのが面倒大変に思えたためです。数の左端もしくは右端を削って素数となる場合に双方向の辺を登録しておけば、付け足す方を考える必要がなくなります。探索済みの素数を覚えておき、同じ素数については探索をスキップします。最初、この処理を入れてなかったため、以下の工夫は考えていたものの、1ケースでTLEが発生して公開するはめに陥りました。処理時間を削減する工夫として、pから探索を始めると候補が多くなると考え、双方向性を活かしてqから始めるようにしました。これにより、初手が必ず端を削ることになるので、候補が少なく済むと考えたのですが...。スキップの処理いれたらあまり意味がなかったような気もします。右隣の桁は削れません。パターンとその両隣が一致しない場合、そもそもパスがないと判断でき、探索を行わないように...としていましたが、これも探索スキップを入れればしなくて良くなりました。...はともかく、提出したRubyのコードは次のようになります。素数のリストを保持するハッシュです。いう、変換回数・途中の変換候補の素数のペアを保持するリストをグルグル処理して、BFSを行っています。C++でmultimapを使って辺を管理するコードを書いてみたので追記します。(追記終わり)終わりに今回は珍しく、数学的なアプローチというよりは、アルゴリズムメインの問題でした。...最初に素数を全部チェックするなんてことをしなければ処理時間的に有利なのはわかっているのですが...。分かり易さをとったということで。)月別アーカイブはてなブログをはじめよう!ange1さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。