Moo University - Team Tryouts(6)

O(N^2)のアルゴリズム
ネットで調べていたら、http://ace.delos.com/MAR04.green.htm見つけた。

We can refine this algorithm by building things up. Suppose we fix minh
and loop through the possibilities for minw in increasing order. As
minw increases, the set of points satisfying the linear constraint gets
strictly bigger. If we sort the points by Ah + Bw, then they will
become valid points in the order they appear (valid in the sense of the
linear constraint, not relative to minw or minh). Thus we can use the
following algorithm:

- Loop over minh
- Loop over minw in increasing order
- add new points to the set of valid points, keeping track of the
last one added (for next time round the loop)
- compare the count to the best so far
- remove the point corresponding to minw from the set

This is now an O(n^2) algorithm, easily fast enough.

おおっ！と思ったが、イマイチよくわからない(´ω｀)しかし予めソートしておくのは間違った方向ではないなぁってことでごにょごにょした結果、実行時間は大幅に短縮された。100ms台も出た。まだ実験段階なのでなんとも言えないが、上位はほとんどO(N^2*logN)のアルゴリズムなんじゃないかという気がしてきた。一位の人だけエラく速いのでO(N^2)の可能性はあるが、メールしても返事くれない。とってもケチんぼ*1だ(｀ω´)

あんまりケチだとインチキコードでビビらすど！とか言ってみる。。。

*1:2位の人は返信してくれた！エラい！！