Hatena::Grouptopcoder

hasiの日記

 | 

2010-05-24

Marathon Match 60 - PolymerPacking

00:40

だめだった。

問題

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14264&pm=10918

リンク先の図のような曲線を、折れ曲がったところで鏡像反転して、折れ線の(xmax-xmin)*(ymax-ymin)を小さくしろ、という問題。

ただし、鏡像反転するときに折れ線が交差したり重なったりしてはいけない。

手法

手法その1

幅優先探索っぽい方法。キューじゃなくてランダムに取り出したり、優先度付きキューにしてみたり。

手法その2

訪問済みかどうか記憶させる処理が無駄っぽかったので、手法その1は却下。

何回もランダムに折り曲げて、最も小さくなる操作を記憶。

時間計測

clock使ってたけど、意図した時間が計れなくて悩まされた。sys/time.hのgettimeofday使ったらうまくいった。

結果

51位。Rating: 1769 → 1707

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/hasi_t/20100524
 |