Google Code Jam Japan 2011(予選) 参戦記

今年初開催の、Google Code Jam Japan 2011に参加しました。

問題を俯瞰した後、Cから解き始めました。Google Code Jamの時にビット演算を利用する問題でミスりましたので、そのリベンジです。提出したのは、Small=44:59,Large=45:59でした。

解き終えた後、お腹が減ったので食事に行きました。ここで、1時間半ほど費やしてしまいました。


続いて、Bに挑戦しました.ランチ中に考えていたため、却ってすぐに解くことができました。貪欲法ですね。提出したのは、Small=2:46:18,Large=2:47:04でした。

せっかくなので、全問提出を目指して、Aに挑戦します。漸化式を作って計算することにより、比較的容易に解くことができました。提出した時間は、Small=3:37:57,Large=3:34:44でした。

結果、満点！
得点:54/54,順位:86/918でした。
問題はこちら。

全部C言語のソースです。

[A.カードシャッフル]

#include<stdio.h>

int main(void){
  int t,m,c,w,a[100],b[100],i,j;
  scanf("%d",&t);
  for(i=1;i<=t;i++){
    scanf("%d %d %d",&m,&c,&w);
    for(j=0;j<c;j++) scanf("%d %d",&a[j],&b[j]);
    for(j=c;j;j--){
      if(w < b[j-1]+1) w+=a[j-1]-1;
      else if(w>=a[j-1]+b[j-1]) continue;
      else w-=b[j-1];
    }
    printf("Case #%d: %d\n",i,w);
  }
  return 0;
}


[B.最高のコーヒー]

#include<stdio.h>
#include<stdlib.h>

#define MIN(x,y) (((x)<(y))?(x):(y))

typedef unsigned long long int llu_int;

typedef struct{
  llu_int cup;
  llu_int kigen;
  llu_int man;
  llu_int can;
  llu_int drink;
}coffee;

int comp(const void *p1,const void *p2);

int main(void){
  coffee *datas;
  llu_int t,i,j,k,l,n,tmp,ans;
  scanf("%llu",&t);
  for(i=1;i<=t;i++){
    scanf("%llu %llu",&n,&k);
    datas=(coffee *)calloc(n,sizeof(coffee));
    for(j=0;j<n;j++){
      scanf("%llu %llu %llu",&((datas+j)->cup),&((datas+j)->kigen),&((datas+j)->man));
      (datas+j)->can=MIN((datas+j)->cup,(datas+j)->kigen);
    }
    qsort(datas,n,sizeof(coffee),comp);
   
    for(j=0;j<n;j++){
      (datas+j)->drink=(datas+j)->can;
      for(l=j+1;l<n;l++){
if((datas+j)->kigen-(datas+j)->drink>=(datas+l)->kigen) continue;
if((datas+j)->kigen<=(datas+l)->kigen){
  (datas+l)->kigen-=(datas+j)->drink;
  (datas+l)->can=MIN((datas+l)->kigen,(datas+l)->cup);
  continue;
}
tmp=(datas+l)->kigen-((datas+j)->kigen-(datas+j)->drink);
(datas+l)->kigen-=tmp;
(datas+l)->can=MIN((datas+l)->kigen,(datas+l)->cup);
      }
    }
    for(ans=0,j=0;j<n;j++) ans+=(datas+j)->drink*(datas+j)->man;
    printf("Case #%llu: %llu\n",i,ans);
    free(datas);
  }
  return 0;
}

int comp(const void *p1,const void *p2){
  coffee n1,n2;
  n1=*(const coffee *)p1;
  n2=*(const coffee *)p2;
  if(n1.man < n2.man) return 1;
  else if(n1.man>n2.man) return -1;
  else return n1.kigen-n2.kigen;
  return 0;
}


[C.ビット数]

#include<stdio.h>

typedef unsigned long long int u_int;

int main(void){
  u_int t,n,ans,flg,i;
  scanf("%llu",&t);
  for(i=1;i<=t;i++){
    scanf("%llu",&n);
    ans=0;
    flg=0;
    while(n!=0){
      if(n&1){
if(flg==0) ans++;
else if(n>>1){
  ans+=2;
  flg=1;
}
      }else{
if(flg==1) ans++;
else{
  ans+=2;
  flg=1;
}
      }
      n>>=1;
    }
    printf("Case #%llu: %llu\n",i,ans);
  }
  return 0;
}