Hatena::Grouptopcoder

じじいのマラソン反省会@TopCoder

ニコニコ生放送:red.cliff.jp
TopCoderでプログラムしてみた(Algorithm Single Round Match専用):http://red.cliff.jp/topcoder.html
 | 

2011-06-29

方針

00:56

今回は反省点が多いのですが、まずは、良さげ見える(が実は良くない)今回の目標と方針を書きます。あとで、失敗した点を書きます。

目標

今までのマラソンマッチでは、最高点が伸びなそうなアルゴリズムだったので、中途半端な順位だった→

「今回はすぐに結果がでないくてもいいから、到達最高点が伸びるような、計算量もギリギリまで使い切るような、スケールの大きいアルゴリズムにする。」

方針が決まるまでの流れ

「たいていの人は頂点数Nが多いときに苦戦するであろう」

→「計算量がNにあまり依存しないアルゴリズムを考えれば勝てるのではないか?」

→「下記のアルゴリズムなら、O(中央の点の数*N)と、Nのオーダーは1乗。しかも、計算量も中央の点を(1,1)おきにとれば、700*700*5000=2450000000で10秒ギリギリぐらい?いけるかも」

→「しかも、この方針は、正10角形を求めるのも、正100角形を求めるのも、かかる時間はそれほど変わらないので、めっちゃ有利」

実際以下の方針を思いつくまでに、10日ぐらい消費してしまいました…

方針

1.まず、中央の点(cx,cy)を決めます。

f:id:shindannin:20110630004526j:image

2.N個の点を極座標に配置します。各点のr,θを求めるのは三角関数で簡単に求まります。

f:id:shindannin:20110630004524j:image

3.座標に分けたので、θ方向に等間隔の座標にあれば、正多角形に近い形になります。

f:id:shindannin:20110630004523j:image

f:id:shindannin:20110630004522j:image

4.結局は、r,θの2次元の座標に落とせるので、「もし、ある(dr,dθ)の範囲内に点があるか調べたい」ときはDPを使えます。

f:id:shindannin:20110630004521j:image

だいたい、「θの範囲、rの範囲がどれぐらいに収まっていれば、正多角形ができるか?」についての基準は、あらかじめ別なプログラムで、sidesDiffとradiiDiffごとに求めておきました(ある半径rのn角形の,範囲dr・dθに点をランダムに配置し、sidesDiffとradiiDiffを満たす多角形ができるか調べる)。実際にこの部分の精度については、かなり高かったので、うまくいってたと思われます。

 |