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

• 問題
• AC

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

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

$\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) = \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 \Bigl( cost_j + \sum_{i \notin S} f(S \cup \{i\})p'_{j,i} + \sum_{i \in S}f(S)p'_{j,i} \Bigr)$

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

$\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 \subsetneq S' \Rightarrow f_j(S') = f(S')$から従う。$S$に含まれているアイドルをすべて持っていて$S$ではない状態に対しては$f_j$と$f$は同一である。） 同様に$f_j(S)$について整理すると$(*)$とまったく同じ式になり、最終的な漸化式は

$\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さんの記事がいちばん参考になった。

UTPC 2013 F - 魔法の糸

• 問題
• AC
• AC (bin sort)

解説を見てACしたのだが、実装でつまづいた……というか、計算量がよくわかっていなかったのでメモ。

頂点$p$を含む連結成分$V(p)$と頂点$q$を含む連結成分$V(q)$を併合するとき、$V(p)$と$V(q)$の間の辺をどう集めるかが問題になるが、重みを隣接行列にでも記録しておいて、単に$V(p)$の頂点と$V(q)$の頂点のペアを総当たりすればよい。こうすると、この部分の計算量が$Q$回の更新で${\mathcal O}(N^2Q)$になってしまいそうな気がしていたのだが、よく見ると1つの頂点ペア$\{v, w\}$につき高々1回しか処理されていないので、${\mathcal O}(N^2+Q)$で済んでいる。

全体の計算量について。Kruskal法の前に辺の長さでソートする部分がボトルネックになる。頂点$p$, $q$を結ぶ$i$個目のクエリに対して、$V(p), V(q)$の間の辺が$d_i$本あったとすると、上で述べたように$d_1+ ... + d_Q \le M$である。また、以前のクエリで$V(p)$の最小全域木を作ろうとした時に選んだ辺は高々$|V(p)|$であり、$V(q)$についても同様に$|V(q)|$である。$|V(p)|+|V(q)| \le N$だから、$i$個目のクエリで扱うべき辺の数は高々$N+d_i$本となる。したがって、$Q$回のソートの計算量は

$\begin{aligned} & {\mathcal O} \bigl (\sum_{i=1}^Q(N+d_i)\log(N+d_i) \bigr) \\ = & \: {\mathcal O} \bigl (\sum_{i=1}^Q(N+d_i)\log N \bigr) \\ = & \: {\mathcal O} \bigl (\sum_{i=1}^Q N \log N + \sum_{i=1}^Q d_i \log N\bigr) \\ \subseteq & \: {\mathcal O} \bigl (QN \log N + M \log N\bigr) \\ \subseteq & \: {\mathcal O} \bigl ((N^2 + M) \log N\bigr). \end{aligned}$

ソートの部分はバケットソートでも通って計算量は${\mathcal O}(N^2+M+Q\max w_i)$となる……けど、別に速くはならない。