# 期待値DPはガチャの役に立つ

前回：

{%preview https://hackmd.io/ZL1-PM4TSsG9cr9elyhoiA %}

もしかして競技プログラミングの役に立つ知識って期待値DPだけですか？確率通りに行くわけないから役に立ってるとも言い難いな　じゃあ競技プログラミングは役に立ちません

けものフレンズのオンラインガチャの開催が発表されました。内容は以下のツイートの画像とリンクを参照してください。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">【<a href="https://twitter.com/hashtag/%E3%81%91%E3%82%82%E3%81%AE%E3%83%95%E3%83%AC%E3%83%B3%E3%82%BA?src=hash&amp;ref_src=twsrc%5Etfw">#けものフレンズ</a>】㊗️10周年！『けものだるまオンラインガチャ』販売開始！🐾<br>限定グッズのラインナップを東京ガチャパークで今すぐチェック！👀<br><br>🌟販売期間🌟 <br>2025年12月23日 12:00 ~ 2026年1月24日 23:59<br><br>💫ガチャはこちら💫<a href="https://t.co/Z5Eb7g6qCK">https://t.co/Z5Eb7g6qCK</a><a href="https://twitter.com/hashtag/%E3%81%91%E3%82%82%E3%83%95%E3%83%AC?src=hash&amp;ref_src=twsrc%5Etfw">#けもフレ</a><a href="https://twitter.com/hashtag/%E3%81%91%E3%82%82%E3%83%95%E3%83%AC10%E5%91%A8%E5%B9%B4?src=hash&amp;ref_src=twsrc%5Etfw">#けもフレ10周年</a>… <a href="https://t.co/GnptwVKdqR">pic.twitter.com/GnptwVKdqR</a></p>&mdash; 東京ガチャパーク【公式】 (@Tokyo_GachaPark) <a href="https://twitter.com/Tokyo_GachaPark/status/2003299533665526219?ref_src=twsrc%5Etfw">December 23, 2025</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

ガチャ1回880円ってなんですか　躊躇の塊なので1回も引けていません　どるちゃほしいんだけど

さて、景品は全部で38種類（←これなに？）なので、$880\times 38=33440$ 円分ガチャ引けばコンプリートできる確率が正になります。でも流石にほぼ必ず被るのは直感的にわかりますね。実際コンプリートするまでに必要な回数、もとい金額の期待値を求めてみましょう。

## 肩慣らし
例によってこの問題は難しいので、肩慣らしとして、すべての景品が出る確率が同じ場合を考えましょう。景品の種類数は同様に38とします。

$1$ 回目は必ずこれまで出たことがないものが出ます。これまで何も出ていないので当たり前ですね。$2$ 回目は、$\frac{1}{38}$ の確率で前と同じ物が出ます。被ってたらもう一度 $\frac{1}{38}$ の確率で失敗するガチャをします。被ってないものが出たら、次は $\frac{2}{38}$、次は $\frac{3}{38}$、…、となって最終的に $\frac{37}{38}$ の確率で失敗するガチャを乗り越えて、コンプリートです。

一般に、確率 $p$ で成功する試行が成功するまでの回数の期待値は $\frac{1}{p}$ です。ちょっとびっくりですが、$p=\frac{1}{x}$ のとき期待値が $x$ 回、と考えると自然だと思います。

というわけで期待値は $1+\frac{38}{37}+\frac{38}{36}+\dots+\frac{38}{1}$ となって、計算してみると $160$ くらいです。$38$ 種類という種類の少なさからは想像できない期待値です。一般に、$n$ 種類のときの期待値は $O(n\log n)$ になります。

## 本題
さて、確率に偏りがあるときはどうなるでしょうか。S賞のとき好きな方を選べるのもややこしいですが、S賞はただ単に $2$ 回引けば良い、と考えればよいです。

$DP[s][a][b][c][d]$ を、S賞を $s$ 種類、A賞を $a$ 種類、…、D賞を $d$ 種類引いてから、コンプするまでの回数の期待値、とします。$(s,a,b,c,d)$ の候補は $3\times 7\times 7\times 13\times 13=24843$ 通りですから、贅沢に全部計算して構いません。

まず、明らかに $DP[2][6][6][12][12]=0$ です。それ以外のときにうまく計算することを考えます。

すでに出たやつが出る確率を計算しましょう。S賞以外は自明です。S賞は、$2$ 回出ているなら $0.01$ でそうでないなら $0$ 、でよいです。そうしたら、何か新しいものを引くまでの回数の期待値は先程と同様に求まります。この値を $n$ とします。

何か新しいものを引いた時、それがS賞、A賞、…、D賞である確率を求めることができます。「新しいものを引く」という条件を無視して確率を求めたのち、全部同じ値で割って和を $1$ にすればよいです。

S賞を引く確率を $p_s$ 、A賞を引く確率を $p_a$ 、…、D賞を引く確率を $p_d$ とすると、

$DP[s][a][b][c][d]=n+DP[s+1][a][b][c][d]\times p_s+DP[s][a+1][b][c][d]\times p_a+ \dots + DP[s][a][b][c][d+1]\times p_d$

となります。長いですね。まあ計算できることはわかったので実装すればよいです。

そうして実装したものが以下になります。（3分クッキング）

https://wandbox.org/permlink/IfILtX2B4Rsb7CaC

間違ってないといいなと思います。計算結果はこうなりました：

337.182325966965 times, 296720.4468509292 yen

…やばいですね。30万円をガチャに費やすな

やっぱり確率が偏ると試行回数も増えるんですね。実は知らなかったので勉強になりました。

ところで、7万円を使った方がいます。期待値の $\frac{1}{4}$ ですが、どうなってるでしょうか：

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">7万払った男の末路 <a href="https://t.co/WFLiIGPjVV">pic.twitter.com/WFLiIGPjVV</a></p>&mdash; りりなすーん (@ririnasoon) <a href="https://twitter.com/ririnasoon/status/2003393905690366423?ref_src=twsrc%5Etfw">December 23, 2025</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

当然ながらコンプはできてないことがわかります。というかこの方はイロワケイルカ推しなのですが、これは何の嫌がらせなんでしょう

## おわりに
おわります。