hotpepsiの練習帳

TCO Marathon R3

23:48

問題 CirclesSeparation

• 平面に円が50～500個程度ランダムで配置される
• それぞれの円は中心座標と半径と重さを持つ
• 円が重ならないように再配置する
• 元の座標からの距離×重さだけスコアが加算される
• スコアを最小化する

やったこと

• 公式のビジュアライザを試すが、Javaなのでデバッグしづらかった
• 素朴な衝突判定と、簡単なビジュアライザを書く
• 重い順に1つずつ配置する
• 中心から元座標への方向をベースに、重なったら距離を伸ばしていく
• 全部配置し終わったら、空いている場所を少し詰める
• 衝突判定をグリッドにした
• 配置順や配置方法を少しずつ変えてみるがスコア改善せず
• 詰めるループを1回単位で呼び出せるようにして、リアルタイム表示できるようにするなど
• 速度を持たせてシミュレーションしようとしたが、重なりが解消できなくて挫折
• 最終的にパラメータをちょっといじったものを提出して70万点くらい

結果

not rated -> 1215

初参加だったがなかなか難しい。

ビジュアライザはこんな感じ。MFCで適当に書いた。配置順(の数字)を中心に書くようにした。

https://github.com/firewood/topcoder/tree/master/mm_81