競プロTweetPocket問題文:http://arc016.contest.atcoder.jp/tasks/arc016_3確率DPっぽい問題です。M種類のガチャがあり、各ガチャには1回引くための金額と、出現アイドルの種類と、各出現アイドルの出現確率が設定されています。最適戦略における、全アイドルをコンプ(コンプリートの略)するために必要な金額の期待値を計算します。例4について考えてみます。アイドルは2人、ガチャは2種類です。アイドルの数が少なくてシンプルすぎないので選びました。1は、1000円で、アイドル1が0.3、アイドル2が0.7の確率で手に入ります。2は、800円で、アイドル1が0.8、アイドル2が0.2の確率で手に入ります。最適な初手(まず最初にどちらのガチャを引くべきか)は分からないです。「片方のアイドルを持っている状態」では、どちらを引くべきかが分かります。例4の遷移のイメージアイドル1のみを持っている場合、アイドル2を引けば終了です。1を繰り返し引いたときに、アイドル2を引くまでの回数の期待値は、1/0.7です。これは幾何分布の期待値です。当たり確率がpのくじを当たるまで引くとき、引く回数の期待値は1/pになります。したがって、アイドル1のみを持っていて、ガチャ1を引き続けようとするとき、支払う残り金額の期待値は、単価×回数の期待値=1000*1/0.7=1428.57...円です。同様に、ガチャ2を引き続けるとき、残り金額の期待値は800*1/0.2=4000円です。どちらを引くべきかは一目瞭然ですね。1のみを引き続けるのが最適です。このとき、残り金額の期待値は1428.57...円です。アイドル2のみを持っている場合も同様に、ガチャ1のみを引く場合の1000/0.3=3333.33...円と、ガチャ2のみを引く場合の800/0.8=1000円を比較して、ガチャ2のみを引く1000円が最適と分かります。アイドル1のみを持っている場合、残り1428.57...円ほど掛かります。アイドル2のみを持っている場合、残り1000円ほど掛かります。初手はどうすべきでしょうか。感覚的には、アイドル2のみの状態に移行したいので、アイドル2を引けそうなガチャに挑戦すべきっぽいですが、単価も考慮しなければいけません。初期状態でガチャ1を引く場合、確実に1000円掛かって、確率0.3で残り金額1428.57...円に、確率0.7で残り金額1000円になります。したがって、この場合の初期状態から掛かる金額の期待値は、1000+0.3*1428.57...+0.7*1000=2128.57...円になります。同様に、初期状態でガチャ2を引く場合、金額の期待値は800+0.8*1428.57...+0.2*1000=2142.86...円になります。したがって、僅差ではありますが、初期状態ではガチャ1を引くのがベストのようです。掛かる金額の期待値は2128.57...円です。以上のように、最後から求めていくと分かりやすいようです。今まであまり注意していませんでしたが、引くべきガチャは現在の所持アイドル状態にのみ依存するという事実があります。幾何分布の無記憶性と呼ばれる概念の本質的には同じでしょうか。コイントスで10回連続表が出たら、次は裏が出る確率の方が表よりも高いだろう、という発想は誤りということです。1を何回か引いたけど所持アイドルしか出なかったので、たまにはガチャ2に変えたら未所持アイドルが出やすいかも、みたいなことはありません。そんなオカルトあり得ません。(ゲームが質の悪い乱数を用いていた場合などはあり得るかもしれませんが、今回はそれは無いとします)したがって、dp[所持状態]=その状態からコンプするまでに掛かる金額の期待値というdpを考えられそうです。小さいので、bitDPで大丈夫ですね。dpの遷移ですが、後ろから決めていくのは良いとして、1つ引っ掛けポイントがあります(引っ掛けポイントじゃないかもしれませんが、私は躓きました)。アイドルが3人である、入力例5の場合を考えましょう。現在、所持状態が[oxx]だとします。oは所持、xは未所持で、左からアイドル1,2,3としましょう(ビットで考えるときは右から1,2,3になるので要注意)。