Codechef 2011 July Cook-off 参戦記

2ヶ月ぶりに、Codechefに参加しました。

問題を2問ほど見ます。Mean Mean Medians は諦めて、Pleasing Chiefにとりかかりました。が、良い解法ができません。1時間ほど費やしましたが、無理そうだったので別の問題に。

Garden Squaresを解き始めます。少々迷ってしまいましたが、1:24に無事にAccepted.

続いて、もうひとつ簡単そうな、Misinterpretationに取り組みます。オーバーフローに悩まされましたが、2:24にSubmit,2:28にAcceptedでした。

問題はこちら。結果、5問中2問正解でした。Short contest ratingが1051.821で、Rankは465になりました。

Garden Squares]

#include<stdio.h>

int main(void){

  int count;

  int t,n,m;

  char board[50][51];

  int i,j,k,l,p,q;

  scanf("%d",&t);

  while(t--){

    scanf("%d %d",&n,&m);

    for(i=0;i<n;i++) scanf("%s",board[i]);

    count=0;

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

      for(j=0;j<m-1;j++){

for(k=j+1;k<m;k++){

  if(board[i][j]!=board[i][k]) continue;

  for(l=i+1;l<n;l++){

    if(board[i][j]!=board[l][j]) continue;

    if(board[i][j]!=board[l][k]) continue;

    if(l-i!=k-j) continue;

    count++;

  }

}

      }

    }

    printf("%d\n",count);   

  }

  return 0;

}

[Misinterpretation]

#include<stdio.h>

#include<string.h>

typedef unsigned  int u_int;

u_int pow26(u_int n);

int main(void){

  u_int check[100001];

  u_int group;

  u_int t,n,i,j,k;

  scanf("%u",&t);

  while(t--){

    memset(check,0,sizeof(check));

    group=0;

    scanf("%u",&n);

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

      if(check[i]==1) continue;

      j=i;

      do{

check[j]=1;

j=(j%2==1)?(n/2+j/2+1):(j/2);

      }while(check[j]==0);

      group++;

    }

    printf("%u\n",pow26(group));

  }

  return 0;

}

u_int pow26(u_int n){

  u_int ret=0,now=1,i;

  while(n--){

    ret=0;

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

      ret+=now;

      ret%=1000000007;

    }

    now=ret;

  }

  return ret;

}