2021/06/11 - ツイートするには長すぎる

まあいいや
競プロ
AtCoder: 3問
その他
刀使ノ巫女 10話, 11話をみた

atcoder.jp 超頂点つくるだけに見える。実際そうなんだけど、UFの内部をmapに変えたり01BFSが必要だったりしてなにかと面倒、グラフから孤立点を取り除いて座圧もどきをするライブラリとかあってもいいかもしれない(なんかバグりそうな見た目してる)

atcoder.jp

これは解説みちゃったんだけど、類似で出そうな問題があるから一応それを書くことに、
正の数列 $A_1,...,A_N$ , $B_1, ... , B_N$ が与えられるたとき集合 $C$ を $C \subset \{ 1,...,N \}$ かつ $|C| \geq K$ と取って、 $\displaystyle X= \sum_{i \in C} A_i$ と、同様に $Y$ を $B$ の $C$ での総和として、(なんかはてなブログでシグマが2つかけない) $\dfrac{X}{Y}$ を最大化する