きろく

特筆すべき記録のまとめ

AtCoder Beginner Contest 120：D - Decayed Bridges

競技プログラミング AtCoder 400 点問題

問題

atcoder.jp

解法

グラフから辺を取り除いていくのではなく，辺を追加していくと考える．辺を後ろから追加していった時の「不便さ」を逆にしたものが求める答えになる．

辺を１つ追加したときに改善される「不便さ」は辺の両端の頂点それぞれが属する頂点の集合の個数をかけたものになる．ただし，両端の頂点が同じ集合に属している場合は「不便さ」は変わらない．これは Union-Find 木を用いて高速に処理することが可能なので O(M) で解ける．

解答

atcoder.jp

f:id:babcs2035:20190311134951p:plain

 

AtCoder Beginner Contest 119：D - Lazy Faith

競技プログラミング AtCoder 400 点問題

問題

atcoder.jp

解法

各クエリごとに x_i より左にある最寄りの神社・寺，x_i より右にある最寄りの神社・寺の場所を計算する．これは std::lower_bound() や std::upper_bound() を用いて O(logA), O(logB) で計算できる．あとは，神社と寺それぞれについて左か右のどちらの最寄りのものにいくかを４通り考え，それぞれでかかるコストを計算する．O(Q * (logA + logB))．

解答

atcoder.jp

f:id:babcs2035:20190311130756p:plain