AGC049 A - Erasing Vertices (400)
類題とかから色々考えるとある点を選んで消す動作をする確率は
$ \frac{1}{その点に到達できる点の数}
求める期待値は全ての点での上の式の和
ある点に到達できる点の数は辺を逆に張ってその点からDFSなりBFSなりで探索する
辺を張る所と期待値を求めるところがそれぞれ
$ O(N^2)
問題:
https://atcoder.jp/contests/agc049/tasks/agc049_a
提出:
https://atcoder.jp/contests/agc049/submissions/18100710
#AGC049
#AGC
#400pt
#A
#AtCoder
#O(N^2)