久々の日記です、今年もTCOの季節になりました。
Round 1の問題は「CutTheRoots 」で、簡単に説明すると植木鉢の中にある植物を根っこをなるべく切り取らないように切り分けるかの問題でした。
図としては下のような感じです。
最初は複数の植物がのびのび成長しています。
これを直線を引いて各自バラバラになるように切り分けます。
この時、下の赤、紫の部分で黒くなった部分がありますが、これは直線で切り分けた際に根っこを切り落としたことを示しています（今回のスコアではこの切落しの長さをいかに少なくするかが争われました）
今回、自分の方針としては貪欲法で
- ランダムに線を大量に引く
- 一番良さそうな線を残す
この2つを植物同士が完全に切り分けられるまで、ひたすら繰り返していました。
1. 与えられた植物同士で完全グラフを作る
今回、終了判定がなかなか難しくて最終的に「完全グラフの辺を全て切断したら終了」というプログラムにしました。最初はドロネー三角分割で生成した線を全部切断したら終了ってやっていたのですが、これだと全て切断しても完全に分けきれていない状態があったので諦めました。
まず最初に初期状態から
完全グラフを作ります（と言っても長すぎる辺は無視してたりしてます）
あとはバッサバッサ辺を切り落としていきます
線を引いて切り落とす
全部切り落としたら終了です
これで切り分け完了です。この直線を選ぶときの評価値としては
- 直線を引いた際に切り落とした根っこの長さの合計 / 切り落としたグラフの辺の数
みたいな評価にしてました（あと、直線上に植物があると切り分け判定でバグったので、その直線は除外とかしてました）
終了後に無駄な直線の排除
切り分け後に、引いた直線を調べて「この直線を取り除いても、全ての辺が削除された状態を維持出来る」場合にその直線を排除する処理をいれました。
高速化
枝が多いと直線と枝の交差判定だけでめちゃめちゃ時間とられたので、その辺りの高速化と、あとは現在の評価値の一番いいやつより良いスコアを出せなくなったら交差判定を即終了とかやってました。
時間調整難しい
やたら自分の提出数が多いのは、今回ちょっと時間管理が難しくてその辺りの調整で迷走した結果です。
感想
本当は焼きなましを使いたいなと思っていましたが実装できませんでした。
Tシャツ欲しかったです（30位以内でもらえた年度ならﾜﾝﾁｬﾝあったかも）
