PKU 2153 Rank List

http://poj.org/problem?id=2153
Li Mingという人がいるクラスの人数分のテストの点数データが渡されるので、それをもとに、点数の累積値でみたLi Mingの順位をテスト毎に答えろというような問題。

最初それぞれのテスト単体で考えるのかと思いました。
普通にやるとTLEしたので、ハッシュ使いました。

typedef struct _node{
  char key[40];
  int val;
  _node* next;
}node;

const int hashMod=30000000;
node* hash[hashMod];
int number;
node ent[10000];

int getnum(char in[]){
  int ha=0;
  for(char*p=in;*p;++p)ha=(ha*67+*p)%hashMod;

  for(node*p=hash[ha];p;p=p->next){
    if(strcmp(in,p->key)==0){
      return p->val;
    }
  }
  node*p=hash[ha];
  hash[ha]=ent+number;
  hash[ha]->next=p;
  strcpy(hash[ha]->key,in);
  hash[ha]->val=number++;
  return number-1;
}

void add(char in[],int val){
  int ha=0;
  for(char*p=in;*p;++p)ha=(ha*67+*p)%hashMod;

  for(node*p=hash[ha];p;p=p->next){
    if(strcmp(in,p->key)==0){
      p->val+=val;
      return;
    }
  }
  node*p=hash[ha];
  hash[ha]=ent+number++;
  hash[ha]->next=p;
  strcpy(hash[ha]->key,in);
  hash[ha]->val=val;
}

char in[40];

main(){
  int n;
  scanf("%d",&n);

  cin.get();
  rep(i,n){
    char in[100];
    gets(in);
  }
  int m;
  cin>>m;
  while(m--){
    int po;
    rep(i,n){
      int val;
      scanf("%d ",&val);
      gets(in);
      add(in,val);
      if(strcmp(in,"Li Ming")==0)po=getnum(in);
    }
    int ans=1;
    rep(i,n)ans+=ent[i].val>po;
    cout<<ans<<endl;
  }
}