あなたが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
r where P(r, n) is greater than or equal
to 0.5 or 50%.
Your code should theoretically handle any non-negative integer
n as input, but we will only be testing your code in
the range of 1 <= n <= 1000000.
For scoring, we will be take the total time required to run
R(n) on inputs 1 through
10000.
We will check if your solutions are correct by running our
version of R(n) on your output to see if
P(your_output, n) >= 0.5 and P(your_output - 1, n) < 0.5, i.e. that your output is actually the
smallest r for a given n.
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
calculate S(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 r between
n and the r we’re looking for, but you do
need to find the smallest r and not just any
r where P(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回の反復しか必要としません。

x_i = log(1 − i/n)
= log((n − i)/n)
cx_i = log(n!/((n −
i − 1)! ⋅ n^{i + 1})
y_i = cx_i
+ cx_{n − i − 2} −
cx_{n − 1} = log binom(n,
i + 1)
z_i = (-1)^{i + 1} ⋅
binom(n, i + 1) ⋅ ((n − i −
1)/n)^r
1 + ∑z_i = n! ⋅ S(r,
n)/n^r =
P(r, n)
z_i ⋅ x_{i +

1} = (-1)^{i + 1} ⋅ binom(n,
i + 1) ⋅ ((n − i −
1)/n)^r log((n − i −
1)/n)
∑z_i ⋅ x_{i +

1} = d/dr P(r, n)

すべての面を見るためにロール！

Python + NumPy、3.95秒

使い方

コメントする返信をキャンセル

Python + NumPy、3.95秒

使い方

コメントする 返信をキャンセル

コメントする返信をキャンセル