Hatena::Grouptopcoder

tanakhの日記 このページをアンテナに追加 RSSフィード

 | 

2009-03-19

TCO Marathon Round 2

09:33 | TCO Marathon Round 2 - tanakhの日記 を含むブックマーク はてなブックマーク - TCO Marathon Round 2 - tanakhの日記 TCO Marathon Round 2 - tanakhの日記 のブックマークコメント

Round1は枠が緩かったので適当に書いて通した。

Round2は自明解では届きそうになかったので、

割とまじめにやらざるを得なかった。

特に問題がなければ、次のラウンドには行けそうな感じ。

問題

いろいろな歯の数のギアがn枚与えられるので、

回転数を最小にするようにK個の平面内でギアを組み合わせろ。

スコアは、配置のbounding boxの面積の逆数の2乗。

解法0

回転数を最小にするには、ギアの歯の数が少ない方半分で、

多い方半分を駆動するだけ。

あとは、その配置を工夫する。

解法1

まずはじめに、自明な解として、一直線上に配置してみた。

100点中35点ぐらいだった。これは全然ダメっぽい。

解法2

次にハニカム状に、60度ずつ折り返しながらジグザグに配置してみた。

それで45点ぐらい。

根本的にダメっぽいなあと思った、

解法3

アイデアが浮かばなくて日曜日ずっと考えてたら、

ハニカムじゃなくて、もっと急角度に折ればいいんじゃないかということに気付く。

というか、こっちの方がはるかに自然だ…。

2分探索で円の交差を調べて、できるだけ急角度に折るようにした。

それで80点ぐらい。

解法4

トップとの面積の差が1割ぐらいぽかったので、

解法3を改良していくことにした。

解法3では、ギアの並びを、

一番小さいギア-一番大きいギア、

二番目に小さいギア-二番目に大きいギア、…

と固定していたので、これの並びを変えて

それに対して解法3を適用して、面積を最小化する。

ギアの並びで焼きなまし。

なんかマラソンやってるといつも焼きなましになるなあ。

これで84点ぐらい。安全圏ぐらいには入ったか。

解法5

焼きなましのコードがバグっていたのを直して、

あとはひたすら解生成を高速化してゆるやかに焼きなます様にして、

近傍の取り方とか変えたりしてみて、ようやく87点ほど。

高速化は、ギアの配置をおおざっぱに求めて、

面積下がってたらちゃんと配置を計算するようにとかなんとか。

向こうのマシンの速度が思ったほど速くなくて、

ちゃんと温度が下がりきっていないっぽくて、

手元での結果と比べてうまく性能が出ていないように見える。

あと、最初clock()で時間切ったら、26秒とかなり余裕を見たはずなのに

TLEしたらしく、かなりスコアが下がった。

gettimeofday()に変えたらなんだか大丈夫っぽい。

感想

問題が焼きなましになってしまえば、

あとはチューニングだけなんだが、

それがかなりめんどくさい。

チューニングを極めても92点ぐらいにしかならなさそう。

トップはもっとスマートな方法なんだろうなあ。


あと、今度からマラソンはC#でやろうと心に決めた。

なんでC#だけキューが別なんだ。

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