「今週のお題：全員が楽しめるファミリーレストラン」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 標準入力から m,n が空白区切りで与えられる時、最大収容人数 m 人のテーブル1卓以上に、合計 n 人が分かれて座る方法が何通りあるかを出力する。ただし、テーブル・人の区別はなく、どのテーブルも 2人以上座るものとする。
要は、n を2～mの数の和に分解する方法ですね。
例えば、m=n=6 の場合であれば、6, 4+2, 3+3, 2+2+2 の4通りとなります。
解説
オーソドックスに漸化式を立てていきます。
まず、補助的なものとして $g(m,n)$ を、「$n$人 ( $n\ge 1$ ) を分けて、最大人数のテーブルが $m$人 ( $m\ge 2$ ) となるパターン数とします。 そうすると、$g(m,n)$は以下の条件を満たします。 $$ \begin{eqnarray} g(2,n)&=&1 &\,&( n:even ) \\ g(2,n)&=&0 &\,&( n:odd ) \\ g(m,n)&=&0&\,&( m \gt 2,\, n\lt m ) \\ g(m,m)&=&1&\,&( m\gt 2 ) \\ g(m,n)&=&\sum_{k=2,m} g(k,n-m)\,\,&\,&( m\gt 2,\,n\gt m ) \end{eqnarray} $$
その上で、本命の $f(m,n)\,\,( n\ge 0,\,m\ge 2 )$ を、次のように定めます。 $$ \begin{eqnarray} f(m,0)&=&1 \\ f(m,n)&=&\sum_{k=2,m} g(k,n)\,\,( n\ge 1 ) \end{eqnarray} $$
こうすることで、$f(m,n)$には次の条件が成立します。その上で、$f(m,n)$がそのまま答えとなります。
$$ \begin{eqnarray} f(2,n)&=&1&\,&( n:even ) \\ f(2,n)&=&0&\,&( n:odd ) \\ f(m,n)&=&f(m-1,n)&\,&( m\ge 3,\,n\lt m ) \\ f(m,n)&=&f(m-1,n)+f(m,n-m)\,&\,&( m\ge 3,\,n\ge m ) \end{eqnarray} $$
この漸化式を回すRubyの実装として、次のコードを提出しました。
p ->m,n{
(1..n+1).map{|i|i&1}.tap{|b|3.upto(m){|i|i.upto(n){|j|b[j]+=b[j-i]}}}[n]
}[*gets.split.map(&:to_i)]
これは、$f(2,0),f(2,1),f(2,2),\cdots,f(2,n)$ を初期値とする配列bに対して、b[j]+=b[j-i] という処理を繰り返して更新していくことで、最終的に $f(m,0),f(m,1),\cdots,f(m,n)$ の配列に変えようというものです。
終わりに
階差と和の関係にある2つの数列/関数を設けることで、問題が分かり易くなることがあるという良い例でしょうか。
