Hatena::Grouptopcoder

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

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

2011-06-29

このアルゴリズムの欠点

00:56

実は、計算量が多くなり、(cx,cy)を調べられる箇所が少ない。

当初の予定では700*700マス(中央がマス上にあるとは限りませんが)調べる予定でしたが、だいたい10000~100000点ぐらいしか調べられませんでした。実は、

(1)r,θを等間隔で細かくとった場合(dr=1,dθ=1)、矩形でO(1)を計算するため、DPで2次元部分和を計算するときが計算量がO(rの分割数(=350)*θの分割数(=360))となり、頂点数Nより大きくなり、そこがボトルネックとなる

(2)r,θを等間隔ではなく、n角形時のdr,dθにあわせてとると、ボトルネックは解消されるが、n角形ごとに計算しなければならない。

最終的には(2)の方針でいきましたが、計算量的にはきつく、多くの(cx,cy)を調べることはできませんでした。

(cx,cy)の位置についての工夫がない。

全く思いつきませんでしたが、多くの人は中央を先に決めるという手法を使ってました。

「(cx,cy)を変えるたびに、N点配置する」ということ自体が損

もし(cx,cy)によらずに、再利用できるデータがあれば、それでも高速化できたはずです。

まぁ、いろいろ試して失敗した点(ひどい焼きなまし法とか)や、反省点(10秒に間に合ってないケースが5つあった)とかは、まだまだありますが、これぐらいで。

 |