enakai00 https://blog.hatena.ne.jp/enakai00/ めもめも https://enakai00.hatenablog.com/ 何の話かと言うと 要素をグループ分けする問題で、よく Union-Find がテクニックとして取り上げられますが、もうちょっと単純に、同じグループの要素に双方向リンクを貼っていって、最後に、グラフ探索で同じグループの要素をまとめるという手法で間に合う場合もあります。 例1 : D - Equals atcoder.jp互いに入れ替え可能な位置を同一グループと見なします。その後、「整数 の位置 が位置 と同じグループに入っている」という条件を満たす の個数を数えればOKです。双方向リンクとグラフ探索による実装はこちら。atcoder.jp 例2 : D - KAIBUNsyo atcoder.j… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fenakai00.hatenablog.com%2Fentry%2F2021%2F07%2F24%2F210512" title="Union-find をグラフ探索で代替できる例 - めもめも" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-07-24 21:05:12 rich https://enakai00.hatenablog.com/entry/2021/07/24/210512 1.0 100%