私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「体積から考える直方体の組み合わせ」（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
入力値を数値にしてsolve()に渡し、結果を印字します。
$Memoは{直方体の体積 => [直方体の3辺のパターン, ...]}の形式である体積になる直方体のパターンをメモしています。
問題を解きます。
retは返却値です。
i,j,kは3つの立方体の体積で、単純に2重ループで列挙しています。
i,j,kは直方体なので任意の整数の体積を取り得るのでこの時点で各直方体の各辺の長さを考慮する必要はありません。
i≦j≦kとなる様にすることでパターンの重複を排除しているのは考え方に書いたとおりです。
当然ですが、i,jが決まったらk=n-i-jになります。
i,j,kが決まったらcount()でその体積を構成する直方体の形状のパターンを数え、retに加算します。
最終的にretが答えなのでこれを返却します。
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の要素数を返しています。
体積がnとなる直方体の各辺のパターンを列挙します。
$Memoにその体積が記録されている場合、計算済みなので$Memoの値を返します。
i,j,kは各辺の長さで、i≦j≦kになる様にします。
jはn/iで割り切れる場合です。
kは(n/i)/jで割り切れる場合、かつj≦kの場合です。
作成したパターンは"iiijjjkkk"の形式の文字列として$Memoに記録します。
$Memoの値を返します。
1回目はリジェクトされたのですが、多分重複があるんだろうと思い確認のためにやってみたコード（Array#uniqで重複を除く）で間に合ってしまったため、それを回答にしてしまいました。
多分、うまい方法があるのだと思います。