私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「掛け算で作るカックロ？」（CodeIQ）を参照してください。
手書きで楽しむパズルとして数独などが人気ですが、計算を使うパズルとして「カックロ」(Wikipedia)があります。
指定された数を1～9の数の「足し算」に分解し、縦と横のマスの条件を満たすように組み合わせて解きます。
この足し算に分解するとき、同じ数を使わないことが特徴です。
ここでは、1～9の数の「掛け算」で似たような作業を行うことを考えます。
例えば、16を3マスに分解すると、1×2×8という分解パターンしかありません。
(2×2×4は同じ数を使っているためNG、1×1×16は1～9の範囲外の数を使っているためNG)
しかし、18を3マスに分解すると、1×2×9の他に1×3×6の分解パターンがあります。
このようにな分解パターンがいくつあるかを考えます。
標準入力から整数 m, n が与えられたとき、1～32768の中で、ちょうど m マスに分解できるのがちょうど n パターンある数がいくつあるか求めてください。
なお、m, n ともに10未満の正の整数とします。
例えば、m = 3, n = 3 のとき、以下の3つが該当します。
分解する前 パターン1 パターン2 パターン3 24 1×3×8 1×4×6 2×3×4 48 1×6×8 2×3×8 2×4×6 72 1×8×9 2×4×9 3×4×6
【入出力サンプル】
標準入力
3 3
標準出力
3
Rubyで解答しています。
#!/usr/bin/ruby
def split(v, m, mn)
# printf("v = %d, m=%d, mn=%d\n", v, m, mn)
if m == 0 then
if v == 1 then return 1
else return 0
end
end
ret = 0
for i in mn..9
next if (v % i) != 0
ret += split(v/i, m-1, i+1)
end
return ret
end
def solve(m, n)
ret = 0
for i in 1..32768
ptn = split(i, m, 1)
# p i if ptn == n
ret += 1 if ptn == n
end
return ret
end
# main
while line = gets
line.strip!
m,n = line.split.map{|a| a.to_i}
p solve(m,n)
end
入力値を数値にしてsolve()に渡し、結果を印字します。
1〜32678の数を順に互いに異なる数で割り、そのパターン数を数えます。この割り算の処理はsplit()で行います。
split()は何パターンの割り方があるか＝何パターンの数の積の形で表されるかを返すので、それがnに等しいかをチェックし、等しければ条件に一致するパターン数としてカウントします。
条件に一致したパターン数はretに記録されるのでそれを返却します。
引数vは分割の対象数です。
mは割り算を行う残りの回数です。
mnは割り算の際に割る数の最小数です。
残りの割り算回数mが0の時に割られる数vが1ならそれまでに割った数の積が元の数になっているので1を返します。それ以外の場合はダメな場合なので0を返します。
retは割り切れたパターン数を記録する変数です。
mn〜9のいずれかの数でvを割った時に余りが0でない場合、うまく割り切れないので無視します。割り切れる場合、次のv=v/i、m=m-1、mn=i+1でsplit()を再帰呼び出しすることで異なる数で順次割る処理を繰り返します。
戻り値はうまく割り切れた時に1、そうでない場合に0なのでこれをretに加算することで、その数を異なる数の積にした場合のパターン数を数えることができます。
1〜32768までで、うまく割り切れない場合が多い（＝途中で0を返す場合が多い）のでメモ化とかしなくても間に合うんじゃないかと思ってやってみたら間に合いました。