babcs2035 https://blog.hatena.ne.jp/babcs2035/ きろく https://babcs2035.hateblo.jp/ 競技プログラミング AtCoder 400 点問題 問題 D - Equals 1~N の順列 p の中で (x,y) 番目のものを swap 出来るとき、最大でいくつの数をもとの位置に戻せるか、という問題。 解法 順列内の数を頂点、swap 出来る関係を辺として図を書いてみると、連結な部分は連結の範囲の中の任意の場所に移動可能だとわかる。あとは、順列内の数と元の場所とが同じ連結部分に属するかを調べたいので Union-Find 木 を使う。シンプル。O(NlogN)。 解答 Submission #2635001 - AtCoder Regular Contest 097 一発 AC だった（うれしいね）。 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbabcs2035.hateblo.jp%2Fentry%2F2018%2F06%2F08%2F221612" title="AtCoder Regular Contest 097 : D - Equals - きろく" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/b/babcs2035/20180608/20180608221424.png Hatena Blog https://hatena.blog 2018-06-08 22:16:12 rich https://babcs2035.hateblo.jp/entry/2018/06/08/221612 1.0 100%