こういうやつの定跡を知っているかが重要そう。 問題 onlinejudge.u-aizu.ac.jp 解法 木から頂点を取り除いていくので、森を扱うことになる。森の連結成分の数は、頂点の数から辺の数を引いたものである。これは期待値にしても変わらず(期待値の線形性)、を…

これが解けないのは悔しいんだけど、まあ難しいね...。 問題 codeforces.com 考察と解法 まず、どの3つのスイッチを取っても、その3つに関わるランプは存在しないという条件に注目する。これは、各ランプについて、押すと影響のあるスイッチは高々2つしかな…