# けものフレンズ3で学ぶ期待値DP

実用上役立つのは緑～水diffくらいまでなんですけどね

この記事はけものフレンズ3のネタバレを含みません

## 想定している読者層
* 期待値DPとなかよくなりたいひと
* ジャパまんをどういうふうに使うのが最適かわからない人

前半部分は期待値DPの説明、後半部分はジャパまんのよさそうな与え方に使います

### Q. 筆者はけもフレ3/競プロの何なの？
A. けもフレ3は初心者です。ハマったばっかで5.5周年記念のおこぼれをいただきました（それでも昨年末あたりからやってはいるんですね…）。
競プロはずっと前からけもフレ3以上にハマっていて、人並み以上の実力は持っているはずです。一応IOI（国際情報オリンピック）の代表をしたりしています。去年割と重要な場所で2回寝坊しました。

### Q. この記事はけものフレンズ3/競技プログラミングの布教ですか？
A. どちらもいいえ。

## 問題設定
以下の問題を考えます。けものフレンズ3のジャパまんで育成するシステムを知っていると理解しやすそうですが、まあ知らなくても問題はないです

> 十分多くのジャパまん[^1]がある。また、$X$ の経験値がほしいフレンズがいる。これから、経験値を $X$ 与えるまで以下の操作を繰り返す。
> * 好きな正整数 $s$ を指定し、ジャパまん $s$ 個をフレンズに与える。指定された確率に従って、以下の $3$ つのどれかが起きる。
> * 使ったジャパまん $1$ 個あたり $3000$ の経験値[^2]がフレンズに与えられる。（成功）
> * 使ったジャパまん $1$ 個あたり $4500=3000\times 1.5$ の経験値がフレンズに与えられる。（大成功）
> * 使ったジャパまん $1$ 個あたり $6000=3000\times 2$ の経験値がフレンズに与えられる。（超成功）
>
>ただし、経験値の合計が $X$ を超えたら、超えた分のジャパまんは返却される。（例：残り経験値が $5000$ のときにジャパまんを $5$ 個使って大成功だったとすると、ジャパまんは $3$ 個返却される。もし超成功であれば $4$ 個返却される。）
> ジャパまんを使う個数を最小化する戦略は？

定式化しましょう。ジャパまん何個分の経験値がほしいかのみが重要であることに注意してください。

> 実数 $X$ と $p+q+r=1$ なる実数の組 $(p,q,r)$ が与えられる。また、$0$ で初期化された変数 $a$ がある。これから、$0\lt X$ の間、以下の操作を繰り返す。
> * 好きな正整数 $s$ を指定する。以下のことが起きる。
> * 確率 $p$ で、$a$ に $\min(s,\lceil X\rceil)$ が加算され、$X$ が $X-s$ に置き換わる。
> * 確率 $q$ で、$a$ に $\min(s,\lceil \frac{X}{1.5}\rceil)$ が加算され、$X$ が $X-1.5\times s$ に置き換わる。
> * 確率 $r$ で、$a$ に $\min(s,\lceil \frac{X}{2}\rceil)$ が加算され、$X$ が $X-2\times s$ に置き換わる。
>
> $a$ の期待値を最小化する戦略は？

$1\leq X\leq 2000$ としましょうか。それ以上ジャパまんが必要な場面を私は知りません。（あったらガチ勢にボコボコにされてきます）

期待値DPを身に着けたい方であればこの定式化が何をしているかは追えるとおもいます（いるかは怪しいですが…本当にジャパまんの与え方を知りたくて読んでる方はこの部分は重要でないでしょう、検証の項が一番重要です）。一応、$\min(s,*)$ という部分は返却を考慮した式になっていることに注意してください。

## 肩慣らし
別にこの問題はそこまで簡単ではないので…、肩慣らしに、もう少し簡単な以下の問題を考えましょう。

> ### [ABC280E - Critical Hit](https://atcoder.jp/contests/abc280/tasks/abc280_e)
> 最初、体力が $N$ であるモンスターが $1$ 体います。
> 高橋くんはモンスターに対し、モンスターの体力が $1$ 以上残っている限り繰り返し攻撃を行います。
> 高橋くんは $1$ 回の攻撃で、$\frac{P}{100}$ の確率でモンスターの体力を $2$ 減らし、$1-\frac{P}{100}$ の確率でモンスターの体力を $1$ 減らします。
> モンスターの体力が $0$ 以下になるまでに行う攻撃回数の期待値を求めてください。
> * $1\leq N\leq 2\times 10^5$
> * $0\leq P\leq 100$

$\bmod 998244353$ のくだりは1mmも重要でないので端折りました。

$DP[i]$ を、体力が $i$ のモンスターを倒すために行う攻撃回数の期待値、とします。自明な部分から処理しましょう。

* $DP[0]=0$：あたりまえですね。未定義な気もしますが定義しておくと後がちょっと楽なので定義しておきます。
* $DP[1]=1$：$P$ の値によらずこうなることが確認できます。

$DP[i]$ $(2\leq i)$ を、$DP[0],DP[1],\dots,DP[i-1]$ が求まっている状態から求めましょう。

つまりこうなります。

* $\frac{P}{100}$ の確率で、$1$ 回の操作でモンスターの体力が $2$ 減る。このあとの攻撃回数は $DP[i-2]$ 回として良い（期待値ってそういうものなので）ので、この場合の期待値は $1+DP[i-2]$ 回
* 同様に、$1-\frac{P}{100}$ の確率で、期待値は $1+DP[i-1]$ 回

ということで、$DP[i]=\frac{P}{100}(1+DP[i-2])+(1-\frac{P}{100})(1+DP[i-1])$ としていいわけです。[^3]これで、この問題は $O(N)$ で解けることがわかります。

これは高橋くんには戦略もくそもなかったわけです。戦略というものが出てくる、以下の問題を考えましょう。

> ### [ABC266E - Throwing the Die](https://atcoder.jp/contests/abc266/tasks/abc266_e)
> サイコロを使ったゲームをします。ゲームは最大 $N$ 回のターンからなり、各ターンは次のように進行します。
> - $1, \dots, 6$ の目が等確率で出る6面ダイスを振り、出目を $X$ とする（出目は各ターンで独立とする）。
> - 現在が $N$ ターン目なら、スコアを $X$ とし、ゲームを終了する。
> - そうでないとき、ゲームを続行するか終了するか選択する。
> - ゲームを終了する場合、スコアを $X$ とし、残りのターンは行わずにゲームを終了する。
>
> スコアの期待値が最大になるように行動したとき、スコアの期待値を求めてください。
> * $1\leq N\leq 100$

そういえばこれ私が初めて解いたE問題ですね

続行するか終了するかに戦略性が出てきました。

とりあえず、$DP[i]$ を、$i$ ターン残っているときの期待値とします。明らかに、$DP[1]=3.5$ です。$DP[i]$ $(2\leq i)$ を求めましょう。

* とりあえず、サイコロを振ります。出た目が $X$ だったとします。
* このとき、振り直さなければスコアは $X$ です。
* 振り直したとき、$1$ ターン消費するのでスコアは $DP[i-1]$ と同一視してよい（！！！）のです。すなわち、$X$ より $DP[i-1]$ のほうが大きければ振り直すべきです。
* つまり $DP[i]=\frac{1}{6}\sum_{k=1}^{6}\max(k,DP[i-1])$ となります。

これも $O(N)$ で解けました。戦略が絡むと言っても実態は全く怖くないですね。

## 本題
とりあえずもとの問題を再掲しておきます。

> 実数 $X$ と $p+q+r=1$ なる実数の組 $(p,q,r)$ が与えられる。また、$0$ で初期化された変数 $a$ がある。これから、$0\lt X$ の間、以下の操作を繰り返す。
> * 好きな正整数 $s$ を指定する。以下のことが起きる。
> * 確率 $p$ で、$a$ に $\min(s,\lceil X\rceil)$ が加算され、$X$ が $X-s$ に置き換わる。
> * 確率 $q$ で、$a$ に $\min(s,\lceil \frac{X}{1.5}\rceil)$ が加算され、$X$ が $X-1.5\times s$ に置き換わる。
> * 確率 $r$ で、$a$ に $\min(s,\lceil \frac{X}{2}\rceil)$ が加算され、$X$ が $X-2\times s$ に置き換わる。
>
> $a$ の期待値を最小化する戦略は？
> * $1\leq X\leq 2000$

実数が出てくるとややこしいので、$s$ として指定できる値を偶数のみにしておきましょう。こうすると、ついでにもとの $X$ も別に整数でいいですね。

一応この変形をした問題を書いておきます。

> **正整数** $X$ と $p+q+r=1$ なる実数の組 $(p,q,r)$ が与えられる。また、$0$ で初期化された変数 $a$ がある。これから、$0\lt X$ の間、以下の操作を繰り返す。
> * 好きな**正の偶数** $s$ を指定する。以下のことが起きる。
> * 確率 $p$ で、$a$ に $\min(\frac{s}{2},\lceil \frac{X}{2}\rceil)$ が加算され、$X$ が $X-s$ に置き換わる。
> * 確率 $q$ で、$a$ に $\min(\frac{s}{2},\lceil \frac{X}{3}\rceil)$ が加算され、$X$ が $X-1.5\times s$ に置き換わる。
> * 確率 $r$ で、$a$ に $\min(\frac{s}{2},\lceil \frac{X}{4}\rceil)$ が加算され、$X$ が $X-2\times s$ に置き換わる。
>
> $a$ の期待値を最小化する戦略は？
> * $1\leq X\leq 4000$

例によって、 $DP[i]$ を $X=i$ のときの答えとしておきましょう。自明な場合として、$i\leq 0$ のとき $DP[i]=0$ です。[^4]$DP[i]$ $(1\leq i)$ はどうやって求めましょうか。

とりあえず、$s$ を固定したときにうまいことやりましょう。とはいえ、これはCritical Hitでやったものそのままなはずです。答えは注釈に書いておくのでやってみてください。[^5]

好きな $s$ を選べる場合はどうでしょうか。これは、単純に $s$ をすべて試して期待値が一番小さいものを採用すればよいです。

$s$ の候補は $O(X)$ 個程度ですから、$O(X^2)$ の計算量でこの問題を解くことができました。

## 検証（競プロ色弱め）
期待値DPの話はだいたいここでおわりです。というわけで、ここで書いたことをコードにして検証してみます。

ところでこんなキャンペーンがありあす。このキャンペーン中にどう使うのが最適か、って話でこの記事を書いているんですがそれはそれ。

> ＼キャンペーン／
>
> ☆フレンズ成長確率超UPキャンペーン☆
フレンズ成長で「大成功」か「超成功」のいずれかのみ発生！
>
> ▼期間
> 2025年5月8日(木) 14:00まで
>
> #けもフレ３ #けものフレンズ
> [午後6:05 · 2025年4月24日 - @kemono_friends3](https://x.com/kemono_friends3/status/1915331127482655188)

とりあえずこれの確率を検証してきました。[^6]多分超成功の確率は $20\%$ っぽいです。つまり $p=0,q=0.8,r=0.2$ としてさっきの問題を解けばいいわけです。

$X$ が $400$ の倍数のときを抜粋してみます。実態は（すべて通常の経験値として）必要なジャパまんの個数は $\frac{X}{2}$ 個なので $x=\frac{X}{2}$ としてそう表示しています。（つまり $x$ が $200$ の倍数のときですね）けもフレ3が分かる人は $x$ のことを「レベルカンストまでジャパまん使用個数を右にトグルしたときの個数」と解釈しておくとよさそうです。

x=200: 124.34574751904681
x=400: 249.33930786912225
x=600: 374.338870112375
x=800: 499.33874377488644
x=1000: 624.338728095058
x=1200: 749.338714490047
x=1400: 874.3387139234412
x=1600: 999.3337262889586
x=1800: 1124.3335696316449
x=2000: 1249.333465037978

うーん、よくわからないですね、だいたい期待値が $6$ 割くらいになることくらいしかわかりません。（$6$ 割くらいになるのは、全部大成功だったとすると $66.666\dots\%$ くらいで、超成功も混ざるならもうすこし割合が下がるから、でしょうか）

よくわからないのはそれはそうで、肝心の戦略がわかっていません。最小値を取る $s$ に対する $\frac{s}{2}$（すなわち、ジャパまんを使うべき個数）を出力してみましょう。$x$ が $100$ の倍数のときに出力するようにします。左が期待値、右が最適な使う個数です。

x=100: (61.84655620268546, 3)
x=200: (124.34574751904681, 1)
x=300: (186.84558601398584, 1)
x=400: (249.33930786912225, 3)
x=500: (311.838931533934, 1)
x=600: (374.338870112375, 1)
x=700: (436.8388658103168, 3)
x=800: (499.33874377488644, 1)
x=900: (561.8387286283529, 1)
x=1000: (624.338728095058, 2)
x=1100: (686.8387280342457, 1)
x=1200: (749.338714490047, 1)
x=1300: (811.8387139690753, 3)
x=1400: (874.3387139234412, 1)
x=1500: (936.8387139169994, 1)
x=1600: (999.3337262889586, 2)
x=1700: (1061.8335870293238, 1)
x=1800: (1124.3335696316449, 1)
x=1900: (1186.833567466173, 3)
x=2000: (1249.333465037978, 1)

`1` とか `2` とか `3` とかありますが、とりあえず $1$ 個刻みくらいに使うのが一番期待値が良いようです。

…ええ、$1$ 個刻みで。

$1$ 個刻みで…

**いや、だるすぎるんですが…**

$1000$ 個もジャパまんを使う場面で $1$ 個ずつ使うとか普通に心が折れます。アニメーションも入るのでなおさら死にます。

あまりにも現実的でなさすぎるので、ひとまず、最低 $\frac{x}{10}$ 個は使うことを強制しましょう。$1000$ 個使うべきときに $100$ 個ずつ使うとかなら…まあいいでしょう。

x=100: (61.85684922952582, 15)
x=200: (124.36388372999562, 20)
x=300: (186.85702732964643, 37)
x=400: (249.3485455323162, 59)
x=500: (311.8526273134021, 56)
x=600: (374.34958751333534, 67)
x=700: (436.8411510711918, 84)
x=800: (499.34620869519864, 80)
x=900: (561.8460423615544, 91)
x=1000: (624.3397925765101, 159)
x=1100: (686.8443525793409, 122)
x=1200: (749.3436831441484, 127)
x=1300: (811.8402380275686, 195)
x=1400: (874.3427554898658, 155)
x=1500: (936.8427832645768, 160)
x=1600: (999.3400879488062, 183)
x=1700: (1061.8420274961418, 179)
x=1800: (1124.3420312439755, 184)
x=1900: (1186.8343165955055, 243)
x=2000: (1249.341535727022, 221)

…おや、あんまり変わらないな？

$0.01$ くらい変わっていますが、まあ $0.01$ なんて誤差の範囲でしょう。デイリーミッションで $15$ 個もらえることは保証されてますし。

もっと厳しく、$\frac{x}{2}$ 個以上使うことを強制します。

x=100: (62.03200000000001, 50)
x=200: (124.7616, 100)
x=300: (187.35168000000002, 150)
x=400: (249.6256, 203)
x=500: (312.29760000000005, 250)
x=600: (374.81728000000004, 300)
x=700: (437.1616, 350)
x=800: (499.80928000000006, 400)
x=900: (562.25088, 450)
x=1000: (624.7552, 500)
x=1100: (687.24288, 550)
x=1200: (749.881344, 600)
x=1300: (812.10688, 650)
x=1400: (874.7084800000001, 700)
x=1500: (937.3149440000001, 750)
x=1600: (999.7004800000001, 800)
x=1700: (1062.2444800000003, 850)
x=1800: (1124.8266240000003, 900)
x=1900: (1187.13408, 950)
x=2000: (1249.83808, 1003)

まあ $0.5$ も誤差なのでこれでもいいでしょう。

もしかしたらあげれるだけあげても良いかもしれません。やってみましょう。

x=100: (62.800000000000004, 100)
x=200: (126.4, 200)
x=300: (190.0, 300)
x=400: (252.8, 400)
x=500: (316.40000000000003, 500)
x=600: (380.0, 600)
x=700: (442.8, 700)
x=800: (506.40000000000003, 800)
x=900: (570.0, 900)
x=1000: (632.8000000000001, 1000)
x=1100: (696.4, 1100)
x=1200: (760.0, 1200)
x=1300: (822.8000000000001, 1300)
x=1400: (886.4000000000001, 1400)
x=1500: (950.0, 1500)
x=1600: (1012.8000000000001, 1600)
x=1700: (1076.4, 1700)
x=1800: (1140.0, 1800)
x=1900: (1202.8000000000002, 1900)
x=2000: (1266.4, 2000)

うーん、流石に有意に差が出てしまいました。あげれる量の半分だけあげる、が手間がかからないし最適解との差があまりないので、まあそれがよさそうです。

### 結論
カンストする量の半分ずつ与えるのが手間と期待値の両方の面で良さそう！

## まとめ
期待値DPは育成の役に立つ！

キャンペーン来る前に育成をするメリットはないのでその検証はしないでおきます。してみたかったらぜひコードを実装してみよう！

### 余談：限界まで与えてもカンストしないとき
安定した量の経験値を得たい場合は小刻みに使うのが良いことが知られています。[^7]知られていますがそれがめんどくさいのは先述の通りなので適当でいいと思います。実際最大値が出る確率を最大化したいなら一気に与えるべきです。$20\%$ の確率でしか当たらないパチンコですが。

### 余談：練習問題
* [ABC300-E](https://atcoder.jp/contests/abc300/tasks/abc300_e)。期待値DPと確率DPは似たようなもんです。
* [ABC326-E](https://atcoder.jp/contests/abc326/tasks/abc326_e)。とある別の（簡単な）典型テクニックを思い出してみましょう。
* [EDPC-J](https://atcoder.jp/contests/dp/tasks/dp_j)。DPをするうえで地味に嫌な要素をうまく排除しましょう。
* [ABC402-E](https://atcoder.jp/contests/abc402/tasks/abc402_e)。これが解けると、期待値DPをある程度理解したと言っていいでしょう。とある別の（少し難しい）典型テクニックを思い出してみましょう。
* 余談ですがこの問題を見て期待値DPの記事を書こうとしました。この問題をどう解くか、みたいな方向に持っていくのは難しかったので今の記事になりましたが…
* [ABC314-E](https://atcoder.jp/contests/abc314/tasks/abc314_e)。難しいです。これが解けたら期待値DPは習得できたようなもんです。

[^1]: フレンズに経験値を与えることができるアイテム
[^2]: 本当はジャパまんの種類によって変わるんですが…　めんどくさいので全属性・大のジャパまんを使ったときの経験値に統一します。
[^3]: $DP[i]=1+\frac{P}{100}\times DP[i-2]+(1-\frac{P}{100})\times DP[i-1]$ とする流派もあると思いますがまあいいでしょう。
[^4]: 今回は $i$ が負の場合も考えます。そのほうが楽だからです。
[^5]: $p\times (\min(\frac{s}{2},\lceil \frac{i}{2}\rceil)+DP[i-s])+q\times (\min(\frac{s}{2},\lceil \frac{i}{3}\rceil)+DP[i-1.5\times s])+r\times (\min(\frac{s}{2},\lceil \frac{i}{4}\rceil)+DP[i-2\times s])$
[^6]: アラビアオリックスさんにジャパまん $1$ 個食わせてどっちが出るか確認、を $50$ 回繰り返しました。
[^7]: 分散が最小化されるのは割と明らかだと思います。