AGC049 A. Erasing Vertices

問題

1からNまで番号のついたN頂点からなる有向グラフが与えられる。
以下の操作をグラフが空になるまで繰り返すとき、操作回数の期待値を求めよ。

• まだ削除されていない頂点を一様ランダムに1つ選び、その頂点および、その頂点から到達可能な頂点をすべて削除する

制約

• 1 <= N <= 100

解法

期待値の線形性から、「Σ (頂点vを選ぶ確率) * 操作回数1回」が答えになる。
「頂点vを選ぶ確率」は、頂点vに到達可能な頂点集合(vを含む)をS(v)とすると、その集合において最初に頂点vが選ばれなければならないので、1/|S(v)|の確率になる。

したがって、S(v)をワーシャルフロイドなどで求めておき、各頂点vの1/|S(v)|の和を求めれば良い。

解法2

(↑の解法は厳しいので、別のアプローチから)
https://twitter.com/homesentinel_/status/1327644375128571905

頂点の選び方は、(削除されていても選ぶと考えると、N!通りある。
サンプル1は、N=3なので、
①２３
①３２
②①３
②３①
③①２
③２①
の順番が考えられる。(3!=6通り)
このうち、頂点を選ぶのは、丸になっているところで、各頂点vについて、丸になっているところを数え上げることを考える。

「その頂点を選んだら頂点vが消えてしまうような頂点の集合S(v)」を考えると、N個のうち、|S(v)|個を選んで、その中では、頂点vが最初に選ばれ、かつ、残りの|S(v)|-1個はどんな並びでも良い。
また、選んでないN-|S(v)|個もどんな並びでも良い。
したがって、Comb(N, |S(v)|) * (|S(v)|-1)! * (N-|S(v)|)!個が頂点vが丸になっている個数になる。

求めたいのは、( Σ(↑の式) ) / N!なので、1/N!をΣの中に入れて、Σ (↑の式)/N!と考えると、
Σ Comb(N, |S(v)|) * (|S(v)|-1)! * (N-|S(v)|)! / N!
= Σ N! / (|S(v)|! * (N-|S(v)|)!) * (|S(v)|-1)! * (N-|S(v)|)! / N!
= Σ (|S(v)|-1)! / |S(v)|!
= Σ 1 / |S(v)|
となる。
したがって、各頂点についてS(v)を求めれば答えが求められる。