PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 307 / チップの欠陥

ある工場では,製造するICチップ n 個あたり k 箇所の欠陥がランダムに生じる。一つのチップにつき複数の欠陥が生じ得る。

3箇所以上の欠陥を持つチップができる確率を p(k,n) とおく。
p(3,7) = 0.0204081633...

p(20,000, 1,000,000) を小数点以下10桁に丸めて 0.abcdefghij の形で答えよ。

Problem 307 - Project Euler

設定の解釈

問題文がちょっとわかりにくいかもしれません。

「チップ n 個あたり k 箇所の欠陥がランダムに生じる」は「確率 k/n で欠陥が生じる」ではなく,「n 個の箱に k 個のボールをランダムに入れる」ととらえるべきです。

箱もボールも区別します。こう考えないと与えられた例の通りになりません。

 p(3, 7)=\dfrac{7}{7^3}=\dfrac{1}{7^2}=0.0204081633\cdots

区別することをはっきりさせるために,箱とボールのかわりに部屋と人で考えます。

「k 人を n 部屋にランダムに割り振ったとき,3人以上の部屋ができる確率を求めよ」

余事象を考える

「少なくとも」ときたら余事象。どの部屋にも m 人以下しか入らない確率を q(m) として

 1-q(1)-q(2)

を求めます。q(1) は簡単です。

 q(1)=\dfrac{{}_n \mathrm{C}_k\cdot k!}{n^k}

q(2) はちょっと面倒です。x 部屋には2人ずつ,y 部屋には1人ずつ入るとします。人数を考えて
2x+y=k

まず y 部屋に1人ずつ入れます。
C[n,y]*C[k,y]*y! 通り

次に x 部屋に2人ずつ入れます。
C[n-y,x]*C[2x,2]*C[2x-2,2]*...*C[2,2] 通り

これらの積を取って,x=1,2,...,[k/2] まで足したものが q(2)です。

以上をもとに計算したら83秒でした。

1分におさめる

q(2) の最後の和の計算で x=0 も含めると q(1) はいりません。また,この和の計算を並列化することで1分を切れました。