AGC049 A - Erasing Vertices - かんプリンの学習記録

問題概要
思考の流れ
提出プログラム
感想

問題概要

${N}$ 頂点の有向グラフが与えられる. グラフが空になるまで以下の操作を繰り返す.

残っている頂点のうちランダムに一つを選び, その頂点およびその頂点から辺をたどって到達できる頂点を削除する.

操作回数の期待値を求めよ.

${1\leq N\leq 100}$

思考の流れ

操作回数を ${X}$ 回とする.
求めるものは ${E[X]=\sum_{k=1}^{N}kP(X=k)}$ で, ${P(X=k)}$ が求められれば良いが削除する頂点の候補の数が選択によって変わっていくので扱いづらく求めるのは困難なので別の方法を考える.

${\downarrow}$

新たに以下の確率変数 ${Y}$ を導入する.

${\begin{equation} Y_v= \left \{ \begin{array}{l} 1　(頂点vを選んだ時) \\ 0　(頂点vを選ばない時) \end{array} \right. \end{equation}}$

これを用いると,
$X=\sum_{v=1}^{N}Y_v$
となる. よって期待値の線形性を用いると,
$E[X]=E[\sum_{v=1}^{N}Y_v]=\sum_{v=1}^{N}E[Y_v]$
したがって, 各頂点について ${E[Y_v]=P(Y_v=1)}$ , つまりその頂点を選ぶ確率を求めればいい.
これは, 頂点 ${v}$ に到達可能な頂点の集合を ${S_v}$ としたときに, ${S_v}$ のどの頂点よりも先に選ばれる必要があるので $P(Y_v=1)=\frac{1}{|S_v|}$ となり, この和が答えとなる.