[AtCoder][ABC194D] コンプガチャをコンプリートするのに必要な回数の期待値

N種類の景品を全て手に入れるには何回ガチャをまわす必要があるのかを考える。
ここで景品が出る確率は全て等しいとする。

下記はこの問題に帰着できる。
AtCoder Beginner Contest 194

STEP1. 期待値の分解

0からN種類まで手に入れるまでのガチャ回数を下記の考え方で分解する。

0種類持っている状態から新しい1種類を手に入れるまでの回数
1種類持っている状態から新しい1種類を手に入れるまでの回数
2種類持っている状態から新しい1種類を手に入れるまでの回数
・・・
N-1種類持っている状態から新しい1種類を手に入れるまでの回数

これらの回数の合計が答えとなる。

言い換えると、
k種類持っている状態から新しい景品が出るまでに必要な回数をX(k)とする
するとN種類手に入れるまでの回数の期待値は下記となる
X(0)+X(1)+...+X(N-1)

STEP2. 期待値の求め方

確率Pで発生する事象が実際に発生するまでに必要な回数の期待値は確率の逆数となる
1/P

直観的には、1/2で発生する事象は2回試せば1回は発生する。とイメージするとわかりやすい
数学的証明は複雑なので省略

X(k)を考えると、k種類持っている状態で残りのN-kから新しい1つを手に入れる確率は
P(k) = (N-k)/N
よって
X(k) = 1/P(k) = N/(N-k)

STEP1と組み合わせることで最終的な答えは下記の式で表すことができる。
N/(N-1) + N/(N-2) + ... + N/(N-(N-1))

参考