「今週のお題：パターゴルフのコース設計」問題解答 ( CodeIQ )

CodeIQ

はじめに

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

codeiq.jp

問題

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

  • 空白区切りで入力される m,n に対し、mホールで合計n打となる、各ホールの打数の割り振り方が何通りあるかを出力する。ただし、各ホールの打数は1以上5以下とする。

解説

次のRubyのコードを提出しました。

def listup(n,s,&b)
  return enum_for(__method__,n,s) unless b
  f=->m,t,u,a{
    t==0 ? b.call(a):
           ((t-1)/m+1..[u,t].min).each{|c|f[m-1,t-c,c,a+[c]]}
  }
  f[n,s-n,4,[]]
end

n,m=gets.split.map(&:to_i)
puts listup(n,m).reduce(0){|s,r|
  t,p,d=n+1
  s+r.reduce(1){|q,c|q*(t-=1)/(d=(p==p=c)?d+1:1)}
}

再帰的に候補を挙げていくのですが、ホール毎に打数を1～5から選んで並べていたのでは、 並べ方の数が爆発する ( と思った ) ため、一旦打数の組み合わせのみを選び、 それぞれに各ホールへの割り振り方をかけて、合計を求めるようにしています。

例えば、4ホール12打数の場合、[4,4,3,1]という組み合わせがありますが、これに対しては 4C2×2C1 の割り振り方があります。

打数の組み合わせの列挙はlistupにより、並びが降順になるように行います。
※前回の連続する桁の数字で作る平方数に味を占めたのか、またEnumeratorとして扱えるようにしています。

なお、打数1～5を0～4にシフトして考える ( 予め総打数からはホール数を引いておく ) ことで、途中で残り打数が0となった時点で再帰を打ち切るようにしています。つまり、打数の組み合わせからは、打数0の部分は省いています。

終わりに

素直にメモ化再帰を使うのとどっちが速かったんでしょうね…。という点は気になりましたが、まあ通ったので特に比較はしていません。