CodeIQ：全員が楽しめるファミリーレストラン

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「全員が楽しめるファミリーレストラン」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

大人数でファミリーレストランに行ったとき、複数のテーブルに分かれて座ることにしました。
このとき、1人だけのテーブルを作ることがないように分けます。

例えば、6人の場合、以下の4通りがあります。
・2人＋2人＋2人
・2人＋4人
・3人＋3人
・6人

1つのテーブルに配置できる最大の人数が m 人のとき、n 人が1つ以上のテーブルに分かれて座る人数のパターンを求めます。
（人数のパターンだけを求め、誰がどのテーブルに座るかは考えないものとします。）

m, n が標準入力からスペース区切りで与えられるとき、このパターン数を標準出力に出力してください。
なお、m, n は 2≦m≦12、2≦n≦1000 を満たす整数とします。

【入出力サンプル】
標準入力

6 6

標準出力

4

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

$Memo = {}

def solve(m,n)
	if $Memo[[m,n]] != nil then return $Memo[[m,n]] end

	if n == 0 then return 1
	elsif n == 1 || n < 0 then return 0
	end

	ret = 0
	mx = n > m ? m : n

	for i in 2..mx
		ret += solve(i, n-i)
	end

	$Memo[[m,n]] = ret
	return ret
end

# main
while line = gets
	line.strip!
	if line.empty? then next end

	m,n = line.split.map{|a| a.to_i}

	p solve(m,n)
end

解説

またもメモ化再帰の問題でした。
これでこの出題者の問題では3連続？

考え方

テーブルに2人以上m人以下を割り当てます。
割り当てた人数をnから引いてまだ残っていたら次のテーブルに同じように割り当てます。
これをn=0になるまで繰り返します。
以上が基本的なロジックです。
これは(m,n)を引数にとる再帰関数を用意すれば容易に実現できます。

終了条件ですがn=0の時はちょうど割り当てができているのでそのパターンを正として1を返します。nが1以下の場合はきちんと割り当てができていないので0を返します。

後は高速化のため同じ計算を省くためにメモ化します。
メモはキーを(m,n)、値をその時のパターン数として用意すればOKです。

main

入力値を数値にしてsolve()に渡し、結果を印字します。

solve(m,n)

再帰関数になっています。
m,nは座席数と残りの人数で初期値は入力値です。
メモに結果があれば計算不要なのでその結果を返却して終わります。
n=0の場合、割り当て完了なので1を返します。
n≦0の場合、割り当て方が不正なので0を返します（なぜかコードではn=1とn<0を別に判断しています）。

mxはテーブルに割り当てられる最大の人数です。n<mの場合は残りの人数までしか割り当てる必要がないのでチェックしてmxを設定しています。

後は2〜mxまでの割り当てに対しsolve(m-1,n-i)を再帰呼び出しし、結果を加算します。

最終的に返却値の合計を返せば答えになります。

雑感

メモ化再帰の問題が続いているので即座にわかりました。
メモ化再帰はとりあえず単なる再帰で実装してみて、その後でメモをどうするか考えると簡単です。