Topcoder Open 2016 Marathon Match(Round 1)の参加日記
結果は55位/136人と振るわなかったが、今後のために記録を残しておく。
問題概要
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16702&pm=10729
- 平面上に、木の幹がランダムに点として存在する
- それぞれの幹からは、ランダムに根が生えている
- 根の終端からまた根もランダムに生えている
- このとき、すべての木の幹が別のグループになるよう、平面を切りたい
- 切断線は無限大の長さになる（＝ある点からある点まで、とは切れない）
- なるべく切られてしまう根を減らして、切断線を求めよ
実装内容
雑な貪欲。すべての幹の組み合わせを求め、幹間の距離が短い順に
- 幹間に線を引き、30等分くらいで切断開始点を決める
- それぞれの開始点から、数度刻みでぐるっと一周で切断面を作ってみる
- 一番、切ってしまった根の長さ合計が少なかったものを採用
を繰り返しただけ。
あとは、すでに切られている幹間は無視したり、根が多すぎるときは単純化して計算量を減らしたりした。
感想と反省
開始3日くらいで実装・提出してから、終了までほぼ改善できずに終わってしまった。
7日目くらいで焼きなましをやってみようとしたのだが、
- 体調などのせいで時間が取れない（そして睡眠不足の悪循環）
- データ構造が良くなくほぼ作り直し
のせいで日の目を見ずにタイムアップ。
まあ3日で何とか黄色を維持できるコードが書けたし、独自Visualizerも悪くない感じにできたので、上達はしているのかもしれない。
教訓
- 時間がない時こそ、実装を急がず戦略を立てて行動する
- プロトタイプといえど、データ構造はなるべく柔軟性を持たせる
