CodeIQ：長男はいつも弟のことを考える？

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「長男はいつも弟のことを考える？」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
長方形の板チョコレートを兄弟で分けて食べることにしました。
このチョコレートは図のようにマス目上になっており、割りやすいようになっています。
これを縦か横に一直線に割って分割します。

割るときは一直線に割るため、チョコレートのマスの途中で割ることはできません。
長男から順に、好きな位置で割って左上から自分の分を取り、残りを次の弟に渡します。
兄弟の人数が与えられるとき、全員が食べられるような分け方が何通りあるかを求めてください。

例えば、縦3マス、横4マスのチョコレートを3人で分けるとき、以下の16通りがあります。
fig.1

標準入力から縦、横、人数が与えられるとき、分け方が何通りあるかを出力してください。
（縦、横のマスの数は最大で20、人数は最大で10人とします。）

【入出力サンプル1】
標準入力
3,4,3
標準出力
16

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

$Memo = {}

def solve(row, col, mem)
	# 最後の1人は割らない
	if row == 0 || col == 0 then return end
	if mem == 1 then
		return 1
	end

	# 計算済みか？
	if $Memo[[row, col, mem]] != nil then
		return $Memo[[row, col, mem]]
	end

	cnt = 0
	# 横に割る
	for r in 1...row
		cnt += solve(row-r, col, mem-1)
	end

	# 縦に割る
	for c in 1...col
		cnt += solve(row, col-c, mem-1)
	end

	$Memo[[row, col, mem]] = cnt

	return cnt
end

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

	input = line.split(",").map{|a| a.to_i}
	p solve(input[0], input[1], input[2])
end

解説

それほど難しくはありません。素直に考えれば解ける問題と思います。
ただし、計算量は多いのでメモ化（動的計画法）などで計算量を減らす必要はあります。

考え方

チョコレートの分割は再帰的な考え方で容易に実現できます。
縦か横に一直線にしか分割しないので長男が割って自分の分をとるというのは行か列を最低1残して数を減らすということです。次男以降は上の兄弟の怒りに対して同じ処理をすれば良いので再帰でシンプルに実現できることがわかります。
ただし、末の弟は分割せずに自分のところに回ってきたものが自分の取り分になります。なのでチョコレートをとっていない兄弟の数をカウンタにしてその値が1になったら終了します。
これが基本的な考え方です。

あとは計算量が多いので計算結果を再利用することを考えます。
(縦,横,残りの人数)に対して何通りの割方があるかが既知ならそのパターン数を記録しておけば十分でしょう（縦と横を入れ替えてもパターン数は同じになるのでそこまで考慮するとさらに計算量を減らせます）。

solve()

引数は行数(row)、列数(col)、兄弟の人数(mem)です。

7行目の処理は末の弟までチョコレートが行き渡らなかった場合です。パターン数に加えないので0を返します。
これを書く段になって気付きましたが、return 0にしなければなりません（Rubyなので正しく動きますがバグでしょう）。 8〜10行目は末の弟の番です。これ以上分割しないのでパターン数1を返します。

13〜15行目は同様のパターンが計算済みかをチェックし、計算済みならメモを参照して返します。これで計算量が削減できます。

19〜21行目と24〜26行目はチョコレートを横と縦に分ける場合の処理です。
チョコレートは1行（列）以上をとって1行（列）以上残して弟に渡す必要があるので1≦自分の取り分<渡ってきたチョコレートの行（列）のパターンだけ分割パターンがあります。
そして、自分の取り分をとったら残りを弟に渡します。自分の取り分をとるという処理は行（列）数を減らすことで表現できます。あとはmemを1減らしてsolve()を再帰呼び出しすればOKです。
再帰呼び出しした結果の値は順次加算して行きます。

28行目で$Memoに計算結果を記録します。$MemoはHashでキーが(縦,横,残りの人数)で値がパターン数です。

最終的にcntを返せば答えになります。

雑感

問題とは関係ありませんが、再帰はわかりにくい手段だと思います（職業プログラマでも再帰を使えない人は結構いると思います）。再帰がわかりにくい理由の一つは行きの処理と戻りの処理があることだと思います。
今回の場合だと行きの処理とは行、列、メンバを減らしながらsolve()を呼び出して行く部分で、戻りの処理はパターン数を加算して行く処理になります。これが離れているというか、最初の行きの処理が戻りとしては最後になるため、途中に間違いがあると全部違うと云う結果になります。なので、デバッグ時に「ここまでは正しい」という確信を持ちづらいのがわかりにくさの一つではないかと思っています。
この問題くらいシンプルならわかりやすいですけど。