MM 95
CirclesMix - Problem:
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16959&compid=58026
CirclesMix - Standings:
続きを読む
-
masashinakata
- 6951
- 0
- 0
- 0
-
- いいね！0
tashikani
@4000Tashikani
方針：画像を1/2に縮小→さらに縮小を15x15くらいになるまで繰り返す。縮小した画像を手本として半径10くらいの円を適当に描く。いくつか円を描いたらひとつ前の画像に復元する。これの繰り返し。
2017-10-12 19:27:48
Yuichi Sayama
@xyz600600
MMお疲れ様でした。 1/27縮小画像 → 1/9 縮小画像 → 1/3 縮小画像 → 1/1 画像と解像度を上げながら、各フェーズで少しずつ円をgreedyに置いていき、解像度上げる毎に置いた円を微妙に上下左右拡大させて調整する感じでした。各フェーズで円を何割置くかは決め打ち
2017-10-12 21:52:12
yowa
@yowa
制限時間20秒がテストに時間かかってアレだったけど、 どうせO(H・W・半径・N)とかのアルゴリズムなんだから、 ローカルテストでざっくり評価するぶんには、入力画像を縦横半分にした上で1/8くらいの時間でやればよかった（こなみ）
2017-10-12 23:05:58
ツカモ
@tsukammo
MM、やるとしたら焼きなましのつもりだったので、貪欲なるほどという感じ。 計算量は必要なだけ画像縮小すればいいだろうと思ってたけど、貪欲の方が良くなるの不思議。
2017-10-12 23:17:00
コルン
@colun
（MMは一時期、焼きなまし系の出題ばかりがなされていたけれども、本来は焼きなまし系がベストになる様な問題は出題ミスも良いところだと思ってる。
2017-10-12 23:20:13
ツカサ し・×・U。
@tsukasa_diary
今回のMMはヒューリスティックかごとごとくダメで、結局焼きなましたんだけど、みんな程うまくいってないので、悲しかった。
2017-10-12 23:23:43