はじめに

CodeIQというところでプログラミング問題「プライム・ホッパー」に解答しましたので、ネタバレです。

codeiq.jp

問題

空白区切りで与えられる入力 p,q ( p,qは素数、p＜q≦10⁵ ) に対し、次のようなpからqへの変換を考えるとき、最小の変換回数 ( 変換する手段がなければ -1 ) を出力する問題です。

変換の手順とは、

元の素数の左端もしくは右端に1～9の数字をつけたして、別の素数にする
ex. 2→23、13→139、3→13、29→229
※ただし、入力で与えられる素数 q を超えてはいけない
元の素数の左端もしくは右端の桁を削って別の素数にする
ex. 31→3、673→67、23→3、673→73
※ただし、103→03=3 のような、上から2桁目が0であるような数の左端を削るのはN.G.

の2種類であり、p=5,q=67 の場合は、次の変換による5回が最小となります。

5→53→3→37→7→67

解説

q以下の素数をノードと見て、ある素数からある素数への変換が可能な場合、辺がつながってると見做すことができ、無向グラフの重み無し最短経路問題として考えることができます。

例えば、上にあった p=5,q=67 の例であれば、67以下の素数の状況を図示すると次のようになります。( 赤い辺が最小変換回数に対応したパス )

f:id:ange1:20160805185050p:plain

そのため、まず各素数に対して、変換可能な素数を辺の情報として挙げてしまい、後はBFSで探索します。最初にq以下の素数を全部調べてしまうため、ムダが多いと言えばそうなのですが、数を付け足す方を調べるのが面倒大変に思えたためです。数の左端もしくは右端を削って素数となる場合に双方向の辺を登録しておけば、付け足す方を考える必要がなくなります。

さて、探索によって経路が途中で全て途絶える場合は問題ありませんが、ループに陥る可能性がありますから、探索済みの素数を覚えておき、同じ素数については探索をスキップします。最初、この処理を入れてなかったため、以下の工夫は考えていたものの、1ケースでTLEが発生して公開するはめに陥りました。

処理時間を削減する工夫として、pから探索を始めると候補が多くなると考え、双方向性を活かしてqから始めるようにしました。これにより、初手が必ず端を削ることになるので、候補が少なく済むと考えたのですが…。スキップの処理いれたらあまり意味がなかったような気もします。

また、ゴールとなる素数につながるパスがない場合もともかくとして、p もしくは qの桁に 0 が含まれる場合、最上位の 0 の左隣、最下位の 0 の右隣の桁は削れません。( 前者は問題上の制約、後者は非素数となるため ) そこで、0～0 のパターンとその両隣が一致しない場合、そもそもパスがないと判断でき、探索を行わないように…としていましたが、これも探索スキップを入れればしなくて良くなりました。いやはや。

…はともかく、提出したRubyのコードは次のようになります。

require 'prime'
x,y=gets.split.map(&:to_i)
pe={}
Prime.each(y){|q|
  next if q<10
  qrtrim=q/10
  if qrtrim.prime?
    (pe[q]||=[]).push(qrtrim)
    (pe[qrtrim]||=[]).push(q)
  end
  qltrim_s=q.to_s[1..-1]
  if qltrim_s[0]!=?0 && (qltrim=qltrim_s.to_i).prime?
    (pe[q]||=[]).push(qltrim)
    (pe[qltrim]||=[]).push(q)
  end
}
ans=-1
if pe[x]&&pe[y] # &&x.to_s[/.(0|0.*0)./]==y.to_s[/.(0|0.*0)./]
  done={y=>true}
  bfsq=[[0,y]]
  while r=bfsq.shift
    d,cur=r
    pe[cur].each{|q|
      break !(ans=d+1) if q==x
      next if done[q]
      bfsq.push([d+1,q])
      done[q]=true
    } or break
  end
end
puts ans

peというのは、ある素数から次に変換できる ( 辿れる ) 素数のリストを保持するハッシュです。コードの前半でq以下の全素数を調べ pe に逐一登録していきます。

コードの後半では、bfsq という、変換回数・途中の変換候補の素数のペアを保持するリストをグルグル処理して、BFSを行っています。なお、x,y というのが問題にある p,q に相当し、おしりの y から探索を始めています。

( 2016/8/6 追記 ) C++でmultimapを使って辺を管理するコードを書いてみたので追記します。

(追記終わり)

終わりに

今回は珍しく、数学的なアプローチというよりは、アルゴリズムメインの問題でした。…最初に素数を全部チェックするなんてことをしなければ処理時間的に有利なのはわかっているのですが…。まあ、分かり易さをとったということで。

ange1のブログ

「プライム・ホッパー」問題解答 ( CodeIQ )

はじめに

問題

解説

終わりに