Kruskal
コンテスト中AC:A〜E C - The Kth Time Query D - Multiply and Rotate E - MST + 1 C - The Kth Time Query 二次元配列を用意し、には、が出現したインデックスを順に記録します。 クエリが与えられた時、まず、のサイズがより小さい場合(出現数が)は、-1を…
解説AC。大体の解法は自分が想定したものと合っていました。 ここでは、を、頂点iに書かれた整数と表現します。 「i番目とj番目が交換可能」という条件を「頂点iと頂点jに無向辺がある」と言い換えます。 昇順に並び替えるとは、 すべての頂点について、とが…
注:解説は独自のものなので、誤った部分がある可能性があります。 コンテスト中はしっかりと証明はできず、実際に書いてみて法則を探しました。証明ができていないと、考慮できていないケースなどが存在する場合が多々あるので、証明できるようにしたいとこ…