CodeIQ:体積から考える直方体の組み合わせ

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「体積から考える直方体の組み合わせ」(CodeIQ)を参照してください。

問題の概要

問題を引用します。
いずれの辺の長さも整数である3つの直方体を考えます。

その直方体の体積の和が与えられたとき、考えられる直方体の組み合わせが何通りあるかを求めてください。
(縦、横、高さを入れ替えたものは一つとカウントします。また、直方体の順番を入れ替えたものも一つとカウントします。)

例えば、体積の和が10のとき、以下の16パターンがあります。

No 一つ目の直方体の縦,横,高さ 二つ目の直方体の縦,横,高さ 三つ目の直方体の縦,横,高さ
1 1, 1, 1 1, 1, 1 1, 1, 8
2 1, 1, 1 1, 1, 1 1, 2, 4
3 1, 1, 1 1, 1, 1 2, 2, 2
4 1, 1, 1 1, 1, 2 1, 1, 7
5 1, 1, 1 1, 1, 3 1, 1, 6
6 1, 1, 1 1, 1, 3 1, 2, 3
7 1, 1, 1 1, 1, 4 1, 1, 5
8 1, 1, 1 1, 2, 2 1, 1, 5
9 1, 1, 2 1, 1, 2 1, 1, 6
10 1, 1, 2 1, 1, 2 1, 2, 3
11 1, 1, 2 1, 1, 3 1, 1, 5
12 1, 1, 2 1, 1, 4 1, 1, 4
13 1, 1, 2 1, 1, 4 1, 2, 2
14 1, 1, 2 1, 2, 2 1, 2, 2
15 1, 1, 3 1, 1, 3 1, 1, 4
16 1, 1, 3 1, 1, 3 1, 2, 2

標準入力から体積の和が与えられるとき、直方体の組み合わせの数を標準出力に出力してください。
なお、体積の和は300以下の整数とします。

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

標準出力
16

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

$Memo = {}

def cuboid(n)
	return $Memo[n] if $Memo[n] != nil

	for i in 1..n
		next if n % i != 0
		m = n / i
		for j in i..n
			next if m % j != 0
			k = m / j
			break if k < j

			$Memo[n] = [] if $Memo[n] == nil
			$Memo[n] << "%03d%03d%03d"%[i,j,k]
		end
	end

	return $Memo[n]
end

def count(i, j, k)
	arr_i = cuboid(i)
	arr_j = cuboid(j)
	arr_k = cuboid(k)

	ret = []

	arr_i.each{|c_i|
		arr_j.each{|c_j|
			next if (i == j) && (c_i < c_i)
			arr_k.each{|c_k|
				next if (j == k) && (c_k < c_j)
				arr = "%s,%s,%s"%[c_i, c_j, c_k].sort
				ret << arr
			}
		}
	}

	return ret.uniq.count
end

def solve(n)
	ret = 0
	for i in 1..n
		for j in i..n
			k = n-i-j
			break if k < j
			ret += count(i, j, k)
		end
	end
	return ret
end

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

	p solve(line.to_i)
end

解説

★★★の問題です。
私のプログラムは「できればいいや」という感じのプログラムであまりよくありません。
うまいコードを書こうと思うと難しいのだと思います。

考え方

処理を二段階にしています。
まず、体積だけに注目して体積の組み合わせを列挙します。
そして、その体積の組み合わせについて、何パターンの組み合わせがあるかを数え、それを全ての体積の組み合わせについて足し合わせます。
これで答えを求められます。

体積の組み合わせについては重複しない様に列挙するのは容易です。
3つの直方体の体積をi,j,kとした場合、i≦j≦kとなる様にすれば重複なく列挙できます。

ある体積の組み合わせについて、それぞれの立方体の形状を重複なく列挙するのはうまくできていません。私はArray#uniqを使って重複を削除してしまいました。

main

入力値を数値にしてsolve()に渡し、結果を印字します。
$Memoは{直方体の体積 => [直方体の3辺のパターン, ...]}の形式である体積になる直方体のパターンをメモしています。

solve(n)

問題を解きます。
retは返却値です。

i,j,kは3つの立方体の体積で、単純に2重ループで列挙しています。
i,j,kは直方体なので任意の整数の体積を取り得るのでこの時点で各直方体の各辺の長さを考慮する必要はありません。
i≦j≦kとなる様にすることでパターンの重複を排除しているのは考え方に書いたとおりです。
当然ですが、i,jが決まったらk=n-i-jになります。

i,j,kが決まったらcount()でその体積を構成する直方体の形状のパターンを数え、retに加算します。

最終的にretが答えなのでこれを返却します。

count(i, j, k)

3つの直方体の形状のパターンを列挙します。

cuboid()はある体積の直方体の形状のパターンを列挙します。
cuboid()の返却値は直方体の各辺をw,h,dとすると、"wwwhhhddd"という9桁の整数の文字列になっています。
これでi,j,kの体積になる直方体のパターンを求めます。

j,j,kそれぞれの体積になる直方体のパターンでループし、"wwwhhhddd"が、iのもの≦jのもの≦kのもの、となる様にピックアップします。これでうまくゆくと思ったのですが、重複を排除しきれないので[iのもの,jのもの,kのもの]という文字列をソートしてコンまで連結した文字列をretに溜めて、最終的にArray#uniqで重複を排除し、retの要素数を返しています。

cuboid(n)

体積がnとなる直方体の各辺のパターンを列挙します。

$Memoにその体積が記録されている場合、計算済みなので$Memoの値を返します。

i,j,kは各辺の長さで、i≦j≦kになる様にします。
jはn/iで割り切れる場合です。
kは(n/i)/jで割り切れる場合、かつj≦kの場合です。
作成したパターンは"iiijjjkkk"の形式の文字列として$Memoに記録します。

$Memoの値を返します。

雑感

1回目はリジェクトされたのですが、多分重複があるんだろうと思い確認のためにやってみたコード(Array#uniqで重複を除く)で間に合ってしまったため、それを回答にしてしまいました。
多分、うまい方法があるのだと思います。