<p><a href="https://atcoder.jp/contests/abc103/tasks/abc103_d">D - Islands War</a></p>
<ul>
<li><img src="https://gyazo.com/ced583d7c3c39017177ebf73093c4243/thumb/1000" alt="image"></li>
<li>考えたこと<ul>
<li>与えられたパスをなるべく少ない回数でカットしたい</li>
<li>あるカットを1つ選んだ時に、それで切れるパスを全部取り除いて、残りについて考える時に、先程のカットは影響しない</li>
<li>ということは「一番端のパスを含んでなるべく多くのパスを切るカット」をグリーディに選んでいけば良いのでは</li>
<li>それで良いのか、良いことの証明は？</li>
</ul>
</li>
<li>公式解説<ul>
<li>僕の方法では「aでソートして一番小さいもののb-1を切る」</li>
<li>公式解説では「bでソートして一番小さいもののb-1を切る」</li>
<li>どういう違いがあるか？</li>
<li>bでソートして一番小さいものがaでも小さい時には差はない</li>
<li>そうでない時<ul>
<li><img src="https://gyazo.com/4d873eb41e26ef7bbe5e0664a2c03efa/thumb/1000" alt="image"></li>
<li>なるほど確かに公式の方が正しい</li>
<li><a href="/ja/%E5%8C%BA%E9%96%93%E3%82%B9%E3%82%B1%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0">区間スケジューリング</a>の貪欲アルゴリズムによく似ている</li>
</ul>
</li>
</ul>
</li>
</ul>


ABC103D