このとき、0.8の確率で、入手済みのアイドル1を入手してしまいます。状態遷移の気持ちとしては、確率0.2で次段階へ移行、0.8で停留となります。以降するまでの回数の期待値はいくらでしょうか。これは、幾何分布の期待値で、1/0.8=1.25となります。1.25回程度3000円を払った後に、次段階へ移行できるのです。移行するときに、[oox]と[oxo]のそれぞれに移行する確率は、0.15と0.05ではありません。足して1にならないのは変です。「停留ではなく移行となった場合に、状態[oox]に移行する確率」は、条件付き確率なので、アイドル2を引く確率/移行する確率=0.15/0.2=0.75となります。同様に、移行するとき、[oxo]に移行する確率は0.05/0.2=0.25です。0.05/0.2*dp[oxo]となります。最初の項は、次段階へ移行するまでに掛かる金額(今回引くガチャ3に支払う金額)の期待値です。残りの項は、例4の場合と同じく「確率*残り金額の期待値」です。例5の遷移のイメージ以上より、dpの更新は以下のようになります。idol[i][j]])iはガチャ番号を表します。idol[i][j])]となります。idol[i][j]は0-indexedになるようにあらかじめデクリメントされています。実際は、メモ化再帰で実現できます。dpの更新は以下のようになります。minimum;}main()関数でdp[(1<<N)-1]=0を代入しておけば、calc(0)が答えになります。実際に提出したコードがこちらです。ポイントは、最適なガチャがアイドル所持状態にのみ依存することと、後ろから埋めていくことですかね。所持状態に依存することが分かって、ビットDP(集合をビット列で表すメモ化再帰)で実現できると分かれば、後ろから埋めるという発想はすぐに浮かびますかね(再帰なら順番を意識しなくても解ける)。遷移の式が難しくて、しっかり考えないと分からないですね。自分は条件付き確率のことを見落としていて時間を溶かしました。最適戦略は、アイドル所持状態→ガチャ、という写像で実現できるので、最小値を更新するたびに最適戦略配列も更新することで戦略の復元も可能です。確率の問題は頭を使う上に検算が面倒なものが多くて大変ですね。kyuuko関連記事AtCoder黄色になる方法こんばんは。誇大広告ぎみなタイトルでごめんなさい。正式タイトルは「AtCoder黄色になるまでに私がしたこと」でお願いします。...記事を読むABC134の初見実況解説動画を投稿しましたこんばんは、ふるやん(@furuya1223)です。今期一番おすすめのアニメは『グランベルム』です。練習セット(EDPC編)こんにちは、ふるやん(@fuurya1223)です。(動的計画法)の練習に関してこんなツイートをしました。■「え、そんなことないよ。F「リボンたたみ」黒魔術解法こんにちは。ICPC国内予選参加記で書いた通り、F問題の自分の解法を書きます。本戦E「ショートコーディング」こんばんは。DDCCの予選通過のメールも無事に届き、2週連続で東京に行くことになりました。練習セット(通常コンテスト編)こんにちは、ふるやん(@fuurya1223)です。使えるようになったりします。前回に引き続き確率の問題ですね。最後、0.05ですね。コメントをキャンセルメールアドレスが公開されることはありません。*サイト次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。クリエイティヴなブログ.当サイトでは利便性向上や閲覧の追跡のためにGoogle・他連携サービスによるCookieが使用されています。サイトの閲覧を続けた場合Cookieの使用に同意したことになります。information.。