betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ AtCoder プログラミング 競技プログラミング お題箱より。 K - 種類数 β 解法 この問題はグラフとして捉えると見通しが良くなります。それぞれの整数を頂点とし、ペア を頂点 と頂点 を結ぶ辺として考えます。整数を選ぶことを頂点に色を塗ることに喩えると、各辺ごとに「両端の頂点のうちどちらかを選んで色を塗る」という操作をして、最終的に色が塗られた頂点の数を最大にすればよいです。 このグラフで非連結な頂点（数字）同士は互いに関係しないので、それぞれの連結成分ごとに考えます。 連結成分に閉路がない場合 すなわち木になっている場合。このときは連結成分の頂点数 とすると辺数が 本であり、全ての頂点を選ぶことはできません。 ある1頂点 を諦めること… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2019%2F06%2F05%2F213138" title="Chokudai SpeedRun 002 K - 種類数 β - ARMERIA" 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/betrue12/20190605/20190605213024.png Hatena Blog https://hatena.blog 2019-06-05 21:31:38 rich https://betrue12.hateblo.jp/entry/2019/06/05/213138 1.0 100%