「今週のお題：素数で作る天秤ばかり」問題解答 ( CodeIQ )

CodeIQ

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • スペース区切りで与えられる入力 m,n に対して、m 以下の素数の重さを持つおもりをそれぞれ1つまで使って、秤で n の重さを測る方法が何通りあるかを出力する。( 秤の左右の状況が反対になっているだけの測り方は同じと見做す )

解説

おもりの使い方は、それぞれ

  • 左に載せる
  • 使わない
  • 右に載せる

の3通りがあります。 そのため、使用できる素数の個数 r に対して 3r 通りの おもりの載せ方が考えられます。

しかし、それを全て試すと r が大きくなった時に破たんするため、 メモ化再帰を行いました。

なお、幾つか使うおもりを決定した後の「残り t を測るために必要なおもりの載せ方」と 「残り-t を測るために必要なおもりの載せ方」は左右逆になるだけで等価なので、 残りの重量が負になる場合は絶対値で考えるようにします。

ということで、次のRubyのコードを提出しました。なお、コード中の再帰関数 f の第2引数 i は、おもりとして使える素数の最小値に対応するインデクス ( 0 開始 ) です。

require'prime'
m,n=gets.split.map(&:to_i)
cand=Prime.each(m).to_a
memo={}
f=->t,i=0{
  memo[[t,i]]||=
    (e=cand[i]) ?
      f[t+e,i+1]+f[t,i+1]+f[(t-e).abs,i+1] :
      t==0 ? 1 : 0
}
p f[n]

終わりに

素直なDPで、特に実行時間的にも問題はなかったので、割とあっさり済んだ問題でした。