n個からm個の特別な要素を考えてその並びの確率を考える
AtCoder
AtCoder400点
AGC-A
青色diff
期待値の線型性
期待値
グラフ問題
強連結成分分解
Floyd-Warshall法
前処理:Floyd-Warshall法
回数の期待値
木の問題に対してパスの場合から考える
条件の言い換え
n個からm個の特別な要素を考えてその並びの確率を考える
面白い。ただ初手で強連結成分分解 (SCC) したくなるのが罠すぎる。SCC 自体は考察過程としては悪くなさそうだけど、SCC して DP...と考えると大変。 問題へのリンク 問題概要 頂点の単純有向グラフが与えられる。以下の操作をグラフが空になるまで繰り返す…