Moo University - Team Tryouts(8)

かなり高速なコード

あれこれ悩んでいるものの、O(n^2)のコードが書けない。しかし最初のコードと比べると同じO(n^2*logn)でも非常に高速なものができた。
まず、h,wの両方をソートしてしまう。もちろんバラバラになると困るので、最初の並び順は記憶(構造体のメンバo)しておく。また、A*h+B*wも配列に格納しておく。h,wを共に降順でソートしておけば、ループカウントが一つ増えるたびにメンバー内の最小h,wが必ず減少する。メンバーに新しく1頭入れては、体格オーバーのウシを外すという作業を繰り返し、メンバー数が最大になったところを記憶しておけばOKということになる。結局、最初の発想と大して変わり無いのだが、メンバーの追加・削除にヒープというデータ構造を使用することにした。このデータ構造だと、最小値・最大値の探索と削除が非常に高速なため、最大でもO(logn)の計算量で行うことが可能だ。k.inabaさんのアルゴリズムは毎回確実にO(logn)かかるわけだから、おなじlognでも結構な差になる。

・・・とは言え、一位の人はどー考えてもn^2でやっているとしか思えないので、まだまだ研究の余地があるのだが、私の力量ではちーと厳しい(;´ω｀)

とりあえず、G++で91msが出たコードを掲載しておく。さっきGCCでヒープを実装したら76msが出たが、誤差を考えればこのコードでも出そうな気がする。。。

#include <cstdio>

#include <algorithm>

using namespace std;
int n,A,B,C;

int i,j,t,minhw,ans;

int heap[1000],sum[1000];

bool check[1000];
struct P{ int d,o; } h[1000],w[1000];
bool cmp(P a,P b){return a.d>b.d;}
int main(){

  scanf("%d%d%d%d",&n,&A,&B,&C);

  for (i=0;i<n;i++){

    scanf("%d%d",&h[i].d,&w[i].d);

    h[i].d*=A;w[i].d*=B;

    h[i].o=w[i].o=i;

    sum[i]=h[i].d+w[i].d;

  }
  sort(h,h+n,cmp);

  sort(w,w+n,cmp);
  for(i=0;i<n;i++){

    check[h[i].o]=1;

    for(j=t=0;j<n;j++){

      minhw=h[i].d+w[j].d;

      if(!check[w[j].o])continue;

      if(sum[w[j].o]-minhw<=C){

        heap[t]=sum[w[j].o];

        t++;

        push_heap(heap,heap+t);

      }
      while(heap[0]-minhw>C&&t){

        pop_heap(heap,heap+t);

        t--;

      }

      ans=t>ans?t:ans;

    }

  }

  printf("%d",ans);

}