ARC016-C「ソーシャルゲーム」

問題文：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の確率で手に入ります。

さて、最適な初手（まず最初にどちらのガチャを引くべきか）は分からないです。

ですが、「片方のアイドルを持っている状態」では、どちらを引くべきかが分かります。

 

 

 

アイドル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を考えられそうです。

今回、アイドルの数は $N\le 10$ なので、$2^N\le 1024$ が十分小さいので、bitDPで大丈夫ですね。

 

さて、dpの遷移ですが、後ろから決めていくのは良いとして、1つ引っ掛けポイントがあります（引っ掛けポイントじゃないかもしれませんが、私は躓きました）。

 

アイドルが3人である、入力例5の場合を考えましょう。

現在、所持状態が[oxx]だとします。oは所持、xは未所持で、左からアイドル1,2,3としましょう（ビットで考えるときは右から1,2,3になるので要注意）。

ガチャ3を引くとします。単価は3000円で、出現確率は{0.8, 0.15, 0.05}です。

このとき、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です。

したがって、[oxx]の状態からガチャ3を引くとき、コンプまでに掛かる金額の期待値は、

3000*1/0.8 + 0.15/0.2*dp[oox] + 0.05/0.2*dp[oxo]

となります。最初の項は、次段階へ移行するまでに掛かる金額（今回引くガチャ3に支払う金額）の期待値です。残りの項は、例4の場合と同じく「確率*残り金額の期待値」です。

 

 

以上より、dpの更新は以下のようになります。

dp[state] = min[i=0~M-1](cost[i]/移行確率+Σ[j=0~C[i]-1のうちidol[i][j]が未入手のもの]p[i][j]/移行確率*dp[state ∪ idol[i][j]])

iはガチャ番号を表します。

dp[state ∪ idol[i][j]]は、stateをビット列で表現すれば、dp[state | (1 << idol[i][j])]となります。ただし、idol[i][j]は0-indexedになるようにあらかじめデクリメントされています。

実際は、メモ化再帰で実現できます。

つまり、dpの更新は以下のようになります。（stateは入手状況をビット列で表現した整数）（実際は実数操作の誤差対策でEPSとか使ってます）

main()関数でdp[(1<<N)-1]=0を代入しておけば、calc(0)が答えになります。

実際に提出したコードがこちらです。

 

ポイントは、最適なガチャがアイドル所持状態にのみ依存することと、後ろから埋めていくことですかね。所持状態に依存することが分かって、ビットDP（集合をビット列で表すメモ化再帰）で実現できると分かれば、後ろから埋めるという発想はすぐに浮かびますかね（再帰なら順番を意識しなくても解ける）。

遷移の式が難しくて、しっかり考えないと分からないですね。自分は条件付き確率のことを見落としていて時間を溶かしました。

最適戦略は、アイドル所持状態→ガチャ、という写像で実現できるので、最小値を更新するたびに最適戦略配列も更新することで戦略の復元も可能です。

 

確率の問題は頭を使う上に検算が面倒なものが多くて大変ですね。