解きました。フィードバックは大変なんでしょうね～。
最初に書いたコードでは、F（12）までとてもとてもまともな時間で計算できなかった。
想定時間30分で12のときまで解くのは結構ハードだと思う。
恥ずかしながら半日～1日くらい？？
【問題】
n 個のリール（数字が描かれている部分です）を持つスロットマシンを回します。
各リールには、0 から 9 のいずれかの数字がランダムに出ます。
このとき、「最も多く出現した数字の出現回数」に等しいドルが賞金として得られます。
例えば n = 6 のスロットマシンを考えましょう。
各リールに、左から順に 7 7 5 1 0 7 という数字が出たとします。
このとき、7 の数字が最も多く 3 回出現していますので、賞金は 3 ドルです。
リールの数字が 0 2 0 9 2 6 のとき、賞金は 2 ドルです。
リールの数字が 1 2 3 4 5 6 のとき、賞金は 1 ドルです。
リールの数字が 8 8 8 8 8 8 のとき、賞金は 6 ドルです。
このスロットマシンを 1 回まわしたときの賞金の期待値を F(n) とします。
例えば F(1) = 1，F(2) = 1.1，F(3) = 1.29 となることが確かめられます。
■ 第１問 （Normal）
F(6) の値を求めて下さい（四捨五入は不要です）。
■ 第２問 （Hard）
F(12) の値を求めて下さい（四捨五入は不要です）。
【方針】
○ nをn以下で10個までの自然数の和に分割する方法が何通りあるかを計算する。
（このとき、同時に賞金ごとに分類しておく）
○ 上で計算した分割方法ごとに、リールの数字が何通りあるかを計算し、期待値を求める。
○ たとえば、n=6で4点のときは、[4, 1, 1], [4, 2] の2通りの分割があり、
それぞれ、 (10*9*8)*(6!/4!)/2!, (10*9)*(6!/4!/2!)/1!通りの組み合わせになる。
配列の長さmについて、(10からmとる順列)*(並べ方の数)/(配列中に同じ数字があれば割引く)通り。（うーん、我ながらわかりにくいか。）
【rubyの提出コード】
#!/usr/bin/env ruby
# -*- coding: utf-8 -*-
BASE=10 # スロットが10進数で回る。
def solve(n)
score_sum=0 # スコアの総和
count_sum=0 # （デバッグ用）スロットの並び方の総和
make_array(n).each{|score, arrays|
arrays.each{|arr| # nと賞金で決まる配列ごとにループ
# 対称性を考慮して、並べ方の数を数える。
# 配列の中の同じ数字があるかどうか。
sym=(1..n).map{|i| arr.count(i)>1 ? arr.count(i) : nil }
.compact.map{|i| facto(i)}.reduce(&:*) || 1
# 上の対称性も考慮した、並べ方の数。
part = facto(n)/arr.map{|i| facto(i)}.reduce(&:*) / sym
# 配列の中の数字にそれぞれ0-9の数字を当てはめる
count = permu(arr.length) * part
count_sum += count
score_sum += score*count
}
}
# print "count(#{n}) = #{count_sum}\n"
score_sum.to_f / BASE**n
end
# 普通の階乗計算
def facto(n)
$facto||=[1]
$facto[n]||=n*facto(n-1)
end
# BASE個の中からn個とる順列
def permu(n)
((BASE + 1 -n)..BASE).reduce(&:*)
end
# nをBASE個までの整数の和に分割し、賞金ごとに分けたHashに配列の配列として格納。
# たとえば n=3 のとき、{1=>[[1, 1, 1]], 2=>[[2, 1]], 3=>[[3]]}を返す。
def make_array(n)
ret = Hash.new{|h,k| h[k]=[] }
min = 1 + (n-1)/BASE
(min..n).map{|sc|
tmp = rec(sc,n).reject{|arr| arr.length > BASE }
ret[sc].push(*tmp)
}
ret
end
# nと賞金が決まった時の、可能な自然数への分割を配列の配列で返す。
def rec(sc,n,ret=[],all=[])
sum = ret.reduce(&:+) || 0
num = n-sum
if n == sum
all << ret
elsif num == sc
ret << sc
all << ret
elsif sc == 1
num.times{ ret << 1 }
all << ret
elsif num > 0 && num >= sc
ret << sc
(1..[sc,n-sc].min).each{|_sc|
rec(_sc,n,ret.dup,all) # 次の数は直前に格納した数字と同じか少ない。
}
else
nil
end
all
end
(1..20).each{|i|
print "F(#{i}) = #{solve(i)}\n"
}