読者です 読者をやめる 読者になる 読者になる

Topcoder Open 2016 Marathon Match(Round 1)の参加日記

C# プログラミングコンテスト マラソンマッチ Topcoder

結果は55位/136人と振るわなかったが、今後のために記録を残しておく。

問題概要
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16702&pm=10729

  • 平面上に、木の幹がランダムに点として存在する
  • それぞれの幹からは、ランダムに根が生えている
  • 根の終端からまた根もランダムに生えている
  • このとき、すべての木の幹が別のグループになるよう、平面を切りたい
  • 切断線は無限大の長さになる(=ある点からある点まで、とは切れない)
  • なるべく切られてしまう根を減らして、切断線を求めよ

実装内容
雑な貪欲。すべての幹の組み合わせを求め、幹間の距離が短い順に

  1. 幹間に線を引き、30等分くらいで切断開始点を決める
  2. それぞれの開始点から、数度刻みでぐるっと一周で切断面を作ってみる
  3. 一番、切ってしまった根の長さ合計が少なかったものを採用

を繰り返しただけ。
あとは、すでに切られている幹間は無視したり、根が多すぎるときは単純化して計算量を減らしたりした。

感想と反省
開始3日くらいで実装・提出してから、終了までほぼ改善できずに終わってしまった。
7日目くらいで焼きなましをやってみようとしたのだが、

  • 体調などのせいで時間が取れない(そして睡眠不足の悪循環)
  • データ構造が良くなくほぼ作り直し

のせいで日の目を見ずにタイムアップ。
まあ3日で何とか黄色を維持できるコードが書けたし、独自Visualizerも悪くない感じにできたので、上達はしているのかもしれない。

教訓

  • 時間がない時こそ、実装を急がず戦略を立てて行動する
  • プロトタイプといえど、データ構造はなるべく柔軟性を持たせる