atcoder.jp 解法 島をノード、橋を辺とするグラフを考える。 グラフの辺を削除するというのを、高速なアルゴリズムで実装するというのは難しい。 そのため、辺の削除をUnionFind-Treeなどを使って辺をつなげていくことで同じことを表現できないかを考えるこ…

atcoder.jp 解法 偶奇にしか興味がないため、mod 2で考えてよい。 次のように場合分けして考える。 のとき と のどちらもが偶数、または奇数であることがわかる。 そのため、どちらかの偶奇が決定されると、もう片方の偶奇も自動的に判明する。 のとき と の…

atcoder.jp ABC214のD問題に似ていたので解きました。 解法 lとrを全探索していたらO(N2)になるため、間に合いません。 なので、個々の要素が答えにどれだけ寄与するか、という主客転倒の考え方を使ってときます。 小さい要素ほど、多くの区間に置いて最小値…