2022-04-01 PAST #9 G - 連結 を解いた
PAST #9: 第九回 アルゴリズム実技検定 G - 連結 を解いた。
問題: https://atcoder.jp/contests/past202112-open/tasks/past202112_g
計算量がよく分からなかった。 10^8 はちょっと危ないかなと思ったんだけど下げる良い手が思いつかなかったので適当に書いたら通った。
大きな方針は 2 つある。 1 つは追加・削除を高速にして表示を低速 (都度探索) にする。もう 1 つは追加・削除を低速にして表示を高速にする。前者は辺の更新のみで都度探索する (O(N^2Q)) 。後者はUnion-Find で辺の追加は高速に、削除時は辺を再度走査して再構築するので低速に、表示は高速だ。こちらの計算量はよく分からない。辺の削除の発生頻度によりそう。ただ頻繁に発生させても O(N^2Q) 程度になる。 O(N^2Q) が 10^8 なので怪しい……。実際には辺はなかなか増えないだろうしそこまでかからないだろうとふんでこれ以上の工夫は諦めた。
削除がややこしい。追加だけなら Union-Find で高速になるのだけど……。
隣接リストを Vec<Vec<_>> で持つと削除時に時間がかかるのも良くないかと思い Vec<BTreeSet<_>> にした。たぶん誤差。
提出: https://atcoder.jp/contests/past202112-open/submissions/30606427 解説: https://atcoder.jp/contests/past202112-open/editorial/3081
今日のコミット。