ysystem57 https://blog.hatena.ne.jp/ysystem57/ ysystemのブログ https://ysystem57.hatenablog.com/ 競プロ Union Find D - Friend Suggestions 解説 問題文が長いですね。結論から言うとこの問題はグラフ問題に帰着できます。今回はUnionFind（以下UF）というデータ構造を使います。グラフやUFについての基本的な内容は他の記事を参照してください。 考察 まず友達関係に関するグラフを作ります。人を、番号のついた頂点とみなします。求めたいものは、各について、頂点と同じ連結成分に属する頂点のうち、頂点に隣接せず、かつ頂点とブロック関係にないものの個数です。図解すると以下のようになります。✔️のついた頂点のうち、ブロック関係にないものの個数を求めます。 実装 まずUFと、頂点の次数を管理するvec… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fysystem57.hatenablog.com%2Fentry%2F2020%2F03%2F02%2F105519" title="AtCoder Beginner Contest 157 参加記 - ysystemのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=i Hatena Blog https://hatena.blog 2020-03-02 10:55:19 rich https://ysystem57.hatenablog.com/entry/2020/03/02/105519 1.0 100%