parukii https://blog.hatena.ne.jp/parukii/ parukiのブログ https://par.hateblo.jp/ 2番目の入力例n=10を考えてみよう。 とりあえず、(i+j) mod (n+1) = 0 となるような辺(i, j)はコスト0なので全部張ろう。 1-10 2-9 3-8 4-7 5-6 あとはコスト1以上の辺を貼るしかない。 実はすべてコスト1の辺で繋げられる。 10+2≡1 9+3≡1 8+4≡1 7+5≡1 よってコストは4。 奇数の場合も同様に考えることができる。したがって解は floor((n-1)/2) クラスカル法っぽくやる 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpar.hateblo.jp%2Fentry%2F2017%2F05%2F05%2F110516" title="Find Amir | Codeforces #411 - parukiのブログ" 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 2017-05-05 11:05:16 rich https://par.hateblo.jp/entry/2017/05/05/110516 1.0 100%