2019年7月30日火曜日

ARC 016 C - ソーシャルゲーム

ARC 016 C - ソーシャルゲーム

既に持っているアイドルの集合S⊆{1,...,N}S \subseteq \{1, ..., N\}が与えられたとき、そこからアイドルをコンプリートするのに必要な金額の期待値をf(S)f(S)としてDPする。

くじjjを引いた時にアイドルiiが出る確率をpj,i′p'_{j, i}とする。くじが1つしかない場合は

f(S)=cost1+∑i∈{1,...,N}f(S∪{i})p1,i′=cost1+∑i∉Sf(S∪{i})p1,i′+∑i∈Sf(S)p1,i′\begin{aligned} f(S) & = cost_1 + \sum_{i \in\{1, ..., N\}} f(S \cup \{i\})p'_{1,i}\\ & = cost_1 + \sum_{i \notin S} f(S \cup \{i\})p'_{1,i} + \sum_{i \in S}f(S)p'_{1,i} \end{aligned}
が成り立つから、f(S)f(S)について解くと
f(S)=(cost1+∑i∉Sf(S∪{i})p1,i′))(1−∑i∈Sp1,i′)−1(∗)f(S) = \bigl( cost_1 + \sum_{i \notin S} f(S \cup \{i\})p'_{1,i} )\bigr) \bigl(1- \sum_{i \in S}p'_{1,i}\bigr)^{-1} \qquad (*)

である。しかし、くじが複数の場合は

f(S)=min⁡j(costj+∑i∉Sf(S∪{i})pj,i′+∑i∈Sf(S)pj,i′)f(S) = \min_j \Bigl( cost_j + \sum_{i \notin S} f(S \cup \{i\})p'_{j,i} + \sum_{i \in S}f(S)p'_{j,i} \Bigr)

となって、これは単純には解けないように見える……が、よく考えると最適な引き方はSSのみによって決まるのだから、状態SSの時にありえる引き方は、新しいアイドルが出るまでくじ11を引き続ける・くじ22を引き続ける・…・くじMMを引き続けるのMM通りである。そこで、手持ちのアイドルがSSの場合にくじjjを引き、それ以外は最適な引き方をする時の期待金額をfjf_jで表すと、f(S)=min⁡jfj(S)f(S) = \min_jf_j(S)である。fjf_jの漸化式も上と同様に書けて

fj(S)=costj+∑i∉Sfj(S∪{i})pj,i′+∑i∈Sfj(S)pj,i′=costj+∑i∉Sf(S∪{i})pj,i′+∑i∈Sfj(S)pj,i′\begin{aligned} f_j(S) & = cost_j + \sum_{i \notin S} f_j(S \cup \{i\})p'_{j,i} + \sum_{i \in S}f_j(S)p'_{j,i} \\ & = cost_j + \sum_{i \notin S} f(S \cup \{i\})p'_{j,i} + \sum_{i \in S}f_j(S)p'_{j,i} \end{aligned}

（二行目はS⊊S′⇒fj(S′)=f(S′)S \subsetneq S' \Rightarrow f_j(S') = f(S')から従う。SSに含まれているアイドルをすべて持っていてSSではない状態に対してはfjf_jとffは同一である。） 同様にfj(S)f_j(S)について整理すると(∗)(*)とまったく同じ式になり、最終的な漸化式は

f(S)=min⁡jfj(S)=min⁡j((costj+∑i∉Sf(S∪{i})pj,i′))(1−∑i∈Spj,i′)−1)\begin{aligned} f(S) & = \min_j f_j(S) \\ & = \min_j \Bigl(\bigl( cost_j + \sum_{i \notin S} f(S \cup \{i\})p'_{j,i} )\bigr) \bigl(1- \sum_{i \in S}p'_{j,i}\bigr)^{-1}\Bigr) \end{aligned}

となる。

http://kyopro.hateblo.jp/entry/2019/07/15/013501
sdfi13jfxさんの記事がいちばん参考になった。

投稿者