Moo University(1)

ウシが持っているデータはh,wという2要素なので、最低2重のループが必要になる。しかもその中でチームに入れるかどうか判定するとなるとどうしても3回ループしなければならない。h,wのループが必ず昇順であれば、無駄な探索をスキップできるのだが、2つの要素h,w（と無駄な計算を省くために予めAh*Bwを計算したものの計3要素を）配列d[N][3]のような形で表現するとすれば、ソートはいずれか一つの要素についてしか出来ない。

たとえば、wについて昇順にソートしておくと、

for(h){
　for(w){
　　...
　}
}

内側のループでは余計な計算を大幅に減らすことができる。しかし外側のループではhが昇順になってないのでスキップすることは出来ない。なんとか外側のループも回数を減らそうと思えば、hの昇順リストを作成しておいて小さい順にループを実行し、for(w){...}の後でhより小さい要素を持ったdを削除してしまえばループをスキップするのと同じ効果が得られる。

最悪計算量を考えると、
1/2*��N(N+1)で単純にN^3のループと比べれば10倍程度の高速化が見込めるが、単純に配列に格納したデータであれば、データを削除する際のコストを無視することは出来ない。リストを作るとそれを高速にソートするルーチンが必要になる。・・・Cだけで書くのはちょっとしんどそうだ。

というか、10倍の速度になったところでN^3の域を脱しているわけではないので、これでも時間制限に引っかかるような気がする。

Acceptされている人たちはどんなコードを書いているのだろうか。。。