2011/10/13

Google Code Jam Japan 2011(決勝) 参戦記

決勝戦に参加しました。

はじめにBを読んで、解けそうだと感じたため、他の問題を読まずに解き始めてしまいます。これが後々大失敗になりました。


1時間30分ほど考えたのですが、どうにもこうにも正しい答えがでません。そこで、気分転換がてらAを読むと、ものの30分もせずに解けてしまいました。どうしてこれを最初にといておかなかったのかと、大変後悔しました。最初に解いていたらTシャツの順位になっていたのに。後の祭りです。

その後、再度Bを考えましたが、どうにも解けませんでした。

コンテストの後のYoutubeの解説を聴く限り、自分のアルゴリズムは正解のようなので、自分のコードの何処かにバグがあるのでしょう。バグをとりきることは出来ませんでした。

結果:得点は15/150,順位は306位でした。問題はこちら

[A,Correct]

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

int comp(const void *p1,const void *p2){
  int n1,n2;
  n1=*((const int *)p1);
  n2=*((const int *)p2);
  return n1-n2;
}

int main(void){
  int k,*ante;
  double S;
  const double pi=atan(1.0)*4;
  int i,j,t;
  double sins;
  scanf("%d",&t);
  for(i=1;i<=t;i++){
    scanf("%d",&k);
    ante=(int *)calloc(k,sizeof(int));
    for(j=0;j<k;j++) scanf("%d",ante+j);
    qsort(ante,k,sizeof(int),comp);
    S=0;
    sins=sin(2*pi/k)*0.5;
    for(j=0;j<k-2;j++) S+=*(ante+j)*(*(ante+j+2))*sins;
    S+=*ante*(*(ante+1))*sins;
    S+=*(ante+k-2)*(*(ante+k-1))*sins;
    printf("Case #%d: %.9f\n",i,S);
    free(ante);
  }
  return 0;
}



[B,Wrong]

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


typedef unsigned long long int ull_int;


ull_int intpow(ull_int a,ull_int b,ull_int c);
ull_int getexp(ull_int now,ull_int bef,ull_int befexp,ull_int c);
ull_int exppow(ull_int a,ull_int b,ull_int c,ull_int min);


int main(void){
  ull_int i,j,k,a,b,c,t;
  ull_int calca,exps;
  scanf("%llu",&t);
  for(i=1;i<=t;i++){
    scanf("%llu %llu %llu",&a,&b,&c);
    calca=a;
    exps=a;
    for(j=0;j<b;j++){
      a=calca;
      calca=intpow(a,exps,c);
      exps=getexp(calca,a,exps,c);
      //printf("calcs=%llu,exps=%llu\n",calca,exps);
    }
    printf("Case #%llu: %llu\n",i,calca);
  }
  return 0;
}


ull_int intpow(ull_int a,ull_int b,ull_int c){
  ull_int res=1;
  while(b>0){
    if(b&1) res=res*a%c;
    a=a*a%c;
    b>>=1;
  }
  return res;
}


ull_int getexp(ull_int now,ull_int bef,ull_int befexp,ull_int c){
  ull_int val=now%c;
  ull_int i,ret,t;
  ull_int *ans;
  ans=(ull_int *)calloc(c,sizeof(ull_int));
  for(i=1;ans[val]==0;i++){
    ans[val]=i;
    val*=now;
    val%=c;
  }
  t=i-ans[val];
  //printf("val,ans[val],i=%llu,%llu,%llu\n",val,ans[val],i);
  ret=exppow(bef,befexp,t,ans[val]);
  free(ans);
  return ret;
}


ull_int exppow(ull_int a,ull_int b,ull_int c,ull_int min){
  ull_int tmp=1;
  ull_int i;
  for(i=1;i<=b;i++){
    tmp*=a;
    if(tmp>=min) break;
  }
  if(tmp<min) return tmp;
  return intpow(a,b,c)-min%c+min;
}

0 件のコメント:

コメントを投稿