ABC103D

https://gyazo.com/ced583d7c3c39017177ebf73093c4243

考えたこと

与えられたパスをなるべく少ない回数でカットしたい

あるカットを1つ選んだ時に、それで切れるパスを全部取り除いて、残りについて考える時に、先程のカットは影響しない

ということは「一番端のパスを含んでなるべく多くのパスを切るカット」をグリーディに選んでいけば良いのでは

それで良いのか、良いことの証明は？

公式解説

僕の方法では「aでソートして一番小さいもののb-1を切る」

公式解説では「bでソートして一番小さいもののb-1を切る」

どういう違いがあるか？

bでソートして一番小さいものがaでも小さい時には差はない

そうでない時

https://gyazo.com/4d873eb41e26ef7bbe5e0664a2c03efa

なるほど確かに公式の方が正しい