TCO 16 Round1参加記録 - CutTheRoots - - simanのブログ久々の日記です、今年もTCOの季節になりました。 Round 1の問題は「CutTheRoots 」で、簡単に説明すると植木鉢の中にある植物を根っこをなるべく切り取らないように切り分けるかの問題でした。 TopCoder 図としては下のような感じです。 最初は複数の植物がのびのび成長しています。 これを直線を引いて各自バラバラになるように切り分けます。 この時、下の赤、紫の部分で黒くなった部分がありますが、これは直線で切り分けた際に根っこを切り落としたことを示しています（今回のスコアではこの切落しの長さをいかに少なくするかが争われました） 今回、自分の方針としては貪欲法で ランダムに線を大量に引く 一番良さそうな線を残す この2つを植物同士が完全に切り分けられるまで、ひたすら繰り返していました。 1. 与えられた植物同士で完全グラフを作る 今回、終了判定がなかなか難しくて最終的に「完全グラ
