「今週のお題：幹事が楽な歓送迎会」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 標準入力から数字 k が与えられる時、次の場合の数を計算し出力する。
- k人が参加する会費￥3,000円の歓送迎会で、幹事が集金する場面において、次の条件を満たす支払い状況が何通りあるか
- 参加者は千円札3枚か、五千円札1枚 ( 要お釣り ) で支払う
- 幹事は最初お釣りを用意していない
- 1人ずつ順番に集金し、かつお釣りが途中で不足しないようにする
例えば k=4 ならば、以下の6通りがありますので、6を出力します。
- 千円×3→千円×3→千円×3→千円×3
- 千円×3→千円×3→千円×3→五千円
- 千円×3→千円×3→五千円→千円×3
- 千円×3→千円×3→五千円→五千円
- 千円×3→五千円→千円×3→千円×3
- 千円×3→五千円→千円×3→五千円
解説
参加者が千円×3か五千円、どちらで支払うかで、幹事にストックされる千円札の枚数が増減し、それによってその後の支払いの受付状況が変わります。そのため、現在ストックされている千円札、残りの参加者という2つのパラメータによって場合の数を管理できると考えます。
これを $f(b,r)$ ( bが千円札、rが残り参加者 ) と置くと、求める答えは $f(0,k)$ と表すことができます。
さて、千円札のストックに余裕があれば五千円札も受け入れられる ( その代わりお釣りのために千円札が2枚減る ) のですが、そうでない場合は、千円札×3 しか受け入れられません。つまり、漸化式としては、次のようになります。
$$ \begin{eqnarray} f(b,r)&=&f(b+3,r-1) &\,&(r\gt 0,\,b\lt 3)\\ f(b,r)&=&f(b+3,r-1)+f(b-2,r-1)&\,&(r\gt 0,\,b\ge 3)\\ \end{eqnarray} $$
さてしかし、途中で千円札に十分余裕ができれば、そこから先は千円札の増減を考える必要がなくなることにも注目します。つまり、その後は千円札・五千円札どちらでも良くて2のべき乗で計算できるということです。そうすると、もはや漸化式を考えずに済むため、効率的に枝刈りできることになります。すなわち、
$$ f(b,r)=2^r\,( b\ge 2r ) $$
これは、終端の $r=0$ のケースも網羅できていることに注意してください。
ということで、提出したコードは、上の計算式を ( 部分的に ) メモ化再帰として実装したものです
p ->k{
(f,h=->m,r{
m>=2*r ? 2**r : m<2 ? f[m+3,r-1] : h[[m,r]]||=f[m-2,r-1]+f[m+3,r-1]
},{})[0][0,k]
}[gets.to_i]
終わりに
新しい年度が始まって、丁度歓送迎会が行われる時期ですね。…悲しいことに、私の場合大体1コインならぬ一葉支払いなので、お釣りを気にしなくて済むんですけど! でも飲まないんですけど! と色々切なくなる問題ではありました。
