あなたが20面のダイを持っているとしましょう。あなたは最終的にすべての20の値をロールバックする前に、そのダイスを転がし始め、数回転がす必要があります。あなたは20の値すべてを見る機会が50％になる前に、何回ロールが必要なのでしょうか？そして、
n 面をすべてロールする前に、 n
面のダイのロールを何回ロールする必要がありますか？
いくつかの調査の後で、 r ロールの後にすべての n
値をローリングするチャンスを計算する式が存在することがわかります。
P(r, n) = n! * S(r, n)/n**r
ここで S（a、b）は第2種のスターリング番号、n個のオブジェクトのセット（各ロール）をk個の空ではないサブセット（各辺）に分割する方法の数。
また、 R（n）と呼ばれる rel=”nofollow noreferrer”>
OEISシーケンスもあります。これは P（r、n）が50％以上の最小の r
に対応します。課題は、このシーケンスの n タームをできるだけ速く計算することです。
課題
- Given an
n, find the smallest
rwhereP(r, n)is greater than or equal
to0.5or 50%. - Your code should theoretically handle any non-negative integer
nas input, but we will only be testing your code in
the range of1 <= n <= 1000000. - For scoring, we will be take the total time required to run
R(n)on inputs1through
10000. - We will check if your solutions are correct by running our
version ofR(n)on your output to see if
P(your_output, n) >= 0.5andP(your_output -, i.e. that your output is actually the
1, n) < 0.5
smallestrfor a givenn. - You may use any definition for
S(a, b)in your
solution. Wikipedia has several definitions
that may be helpful here. - You may use built-ins in your solutions, including those that
calculateS(a, b), or even those that calculate
P(r, n)directly. - You can hardcode up to 1000 values of
R(n)and a
million Stirling numbers, though neither of these are hard limits,
and can be changed if you can make a convincing argument for
raising or lowering them. - You don’t need to check every possible
rbetween
nand therwe’re looking for, but you do
need to find the smallestrand not just any
rwhereP(r, n) >= 0.5. - Your program must use a language that is freely runnable on
Windows 10.
ソリューションをテストするコンピュータの仕様は、 i7 4790k、8 GB RAM です。
@DJMcMayhem
のおかげでテスト用にコンピュータを提供できました。参考までにあなた自身の非公式タイミングを自由に追加できますが、公式のタイミングはDJがテストできるようになると後で提供されます。
テストケース
n R(n)
1 1
2 2
3 5
4 7
5 10
6 13
20 67 # our 20-sided die
52 225 # how many cards from a huge uniformly random pile until we get a full deck
100 497
366 2294 # number of people for to get 366 distinct birthdays
1000 7274
2000 15934
5000 44418
10000 95768
100000 1187943
1000000 14182022
ご質問やご提案がありましたら教えてください。幸運と良い最適化！
Python + NumPy、3.95秒
from __future__ import division
import numpy as np
def rolls(n):
if n == 1:
return 1
r = n * (np.log(n) - np.log(np.log(2)))
x = np.log1p(np.arange(n)/-n)
cx = x.cumsum()
y = cx[:-1] + cx[-2::-1] - cx[-1]
while True:
r0 = np.round(r)
z = np.exp(y + r0 * x[1:])
z[::2] *= -1
r = r0 - (z.sum() + 0.5)/z.dot(x[1:])
if abs(r - r0) < 0.75:
return np.ceil(r).astype(int)
for n in [1, 2, 3, 4, 5, 6, 20, 52, 100, 366, 1000, 2000, 5000, 10000, 100000, 1000000]:
print('R({}) = {}'.format(n, rolls(n)))
import timeit
print('Benchmark: {:.2f}s'.format(timeit.timeit(lambda: sum(map(rolls, range(1, 10001))), number=1)))
オンラインで試してみてください！
使い方
これは r （ r 、 n ）、 P （
r 、 n r をニュートンの方法で検索するには、 >）= 0.5で、各ステップの前に
r を整数に丸め、ステップが r
を3/4未満移動するまで繰り返す。最初の推測では、これは通常、1回または2回の反復しか必要としません。
xi = log(1 − i/n)
= log((n − i)/n)
cxi = log(n!/((n −
i − 1)! ⋅ ni + 1)
yi = cxi
+ cxn − i − 2 −
cxn − 1 = log binom(n,
i + 1)
zi = (-1)i + 1 ⋅
binom(n, i + 1) ⋅ ((n − i −
1)/n)r
1 + ∑zi = n! ⋅ S(r,
n)/nr =
P(r, n)
zi ⋅ xi +
1 = (-1)i + 1 ⋅ binom(n,
i + 1) ⋅ ((n − i −
1)/n)r log((n − i −
1)/n)
∑zi ⋅ xi +
1 = d/dr P(r, n)