考え方 回答例 (Functional Graphであることを利用) 回答例 (UnionFind) 考え方$x$から$A_{x}$に辺を張った有向グラフを考える． グラフの閉路に含まれる頂点であることが，高橋君の勝つ必要十分条件． この頂点の個数をカウントすれば良い．アライグマ「E問…

考え方 回答例 考え方「辺を切る問題」は，逆順に考えて「辺をつなぐ問題」に読み替える事を考えると，UnionFind（UnionFind木 - 競プロはじめました）が使える．UnionFindの初期化では， すべての発電所をつなぐ イベントで切られない辺をつなぐ とすればよ…

考え方 回答例 考え方左から見ていくと，コの字の辺を追加していく形になっている（初期状態のみ特殊）．各ステップで3辺のうちどれを切るかをきめるとdpで解ける．dp[i][j][k]を， 左から$i$番目まで決まっていて， $j$本の辺を取り除かれていて， 上と下が…

考え方 回答例 考え方$0$$,1, 2, ..., N$を頂点とするグラフで考える．「$(l, r)$が与えられる」を「頂点$(l - 1)$と頂点$r$の間に（無向）辺が張られる」と読み替えれば，\begin{aligned} & a_{1} + a_{2} + \cdots a_{N} \text{が計算できる} \\ &\Leftrig…