Codechef 2011 May cook 参戦記

Codechefに初参加したので、その参戦記です。

開始後、とりあえず、一番おいしそうな名前の(本当にそういう理由です)"Popular Rice Recipe"に挑戦します。難しくありません、昨日のTopcoderでも似たような問題がありましたが、今度はCですのでもっと楽です。14minでaccept。

ですが、これ以降が情けないのです。

次に人数の多い、"Socializing Game around Pizza"に挑戦しますが、なかなかうまくいきません。幾つか予想をたてて、証明も考えました。
予想1:Bが勝つものに2,3を足したものはAが勝てる(これは理由があって、問題文から、Aは「Bが勝つ」形にピザを変形できます。Bが勝つ=その段階での後手が勝つ、なのでこの場合Aが勝てます。)
予想2:偶数ならAが勝つ(線対称に切って、対称性を崩さないようにすれば勝てます)。
まではうまく行ったのですが、ここから「4で割って１余るときだけBがかつ」としたのは勇み足でした。42minでWrong Answer。いろいろ考えるも、奇数の場合の処理が思いつかず、お手上げです。

仕方がないので戻ってみると、"Distribute idlis Equally"のほうが増えていたので、それを解きます。マージソートで実装して、次いでストランドソートを使いましたが、どちらもTLE。どうしたらよかったのでしょうか。

この段階で諦めて、1/5でした。コンペティションサイトはこちら。

恒例のソース公開です。
"Popular Rice Recipe"
極めて単純に組みました。

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

typedef struct{
  char name[21];
  char sign;
} user;

int main(void){
  int t,n,point;
  int i,j,k,flg,usercount;
  user *users;
  char names[21],signs;
  scanf("%d",&t);
  for(i=0;i<t;i++){
    scanf("%d",&n);
    users=(user *)calloc(n,sizeof(user));
    usercount=0;
    for(j=0;j<n;j++){
      scanf("%s %c",names,&signs);
      flg=0;
      for(k=0;k<usercount;k++){
if(strcmp((users+k)->name,names)==0){
 flg=1;
 (users+k)->sign=signs;
 break;
}
      }
      if(flg==0){
(users+usercount)->sign=signs;
strcpy((users+usercount)->name,names);
usercount++;
      }
    }
    point=0;
    for(j=0;j<usercount;j++){
      if((users+j)->sign=='+') point++;
      else if((users+j)->sign=='-') point--;
    }
    printf("%d\n",point);
  }
  free(users);
  return 0;
}


"Socializing Game around Pizza"
先の「間違った予想」版です。

#include<stdio.h>

int main(void){
  int n,in,i;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&in);
    if(in%4==1) puts("Bhima");
    else puts("Arjuna");
  }
  return 0;
}


"Distribute idlis Equally"
TLEなので解答は多分あっているのでしょう。いかほど遅いのでしょうか？

#include<stdio.h>
#include<stdlib.h>
#define SIZE 3000

void merge(int a[], int asize, int b[], int bsize, int c[], int csize);
void strandsort(int data[], int num);

int main(void){
  int t,n,idils[SIZE],i,j,k;
  int sum,count,tmp1,tmp2,flg;
  scanf("%d",&t);
  for(i=0;i<t;i++){
    scanf("%d",&n);
    sum=0;
    for(j=0;j<n;j++){
      scanf("%d",idils+j);
      sum+=*(idils+j);
    }
    if(sum%n!=0){
      puts("-1");
      continue;
    }
    sum/=n;
    strandsort(idils,n);
    count=0;
    while(idils[0]!=sum){
      count++;
      k=(idils[n-1]-idils[0]+1)/2;
      idils[n-1]-=k;
      idils[0]+=k;
      strandsort(idils,n);
    }
    printf("%d\n",count);
  }
  return 0;
}

void merge(int a[], int asize, int b[], int bsize, int c[], int csize) {
  int i, j = 0, k = 0;
  for (i = 0; i < csize; i++) {
    if (j >= asize) {
      c[i] = b[k];
      k++;
      continue;
    }else if (k >= bsize) {
      c[i] = a[j];
      j++;
      continue;
    }
    if (a[j] > b[k]) {
      c[i] = b[k];
      k++;
    }else{
      c[i] = a[j];
      j++;
    }
  }
}

void strandsort(int data[], int num) {
  int sub[SIZE],res[SIZE],sub_ct=0,res_ct=0,tmp[SIZE];
  int i,j,k;
  while(res_ct<num){
    for(i=0;i<num;i++){
      if(data[i]==-1) continue;
      if(sub_ct==0){
sub[0]=data[i];
data[i]=-1;
sub_ct++;
      }else if(sub[sub_ct-1]<=data[i]){
sub[sub_ct]=data[i];
data[i]=-1;
sub_ct++;
      }
    }
    if(res_ct==0){
      res_ct+=sub_ct;
      for(i=0;i<sub_ct;i++) res[i]=sub[i];
      sub_ct=0;
    }else{
      merge(sub,sub_ct,res,res_ct,tmp,sub_ct+res_ct);
      res_ct+=sub_ct;
      for(i=0;i<res_ct;i++) res[i]=tmp[i];
      sub_ct=0;
    }
  }
  for(i=0;i<num;i++) data[i]=res[i];
  return;
}