2011年3月31日木曜日

Codeforces Beta Round #65(Div.2) 参戦記

恒例になってきた感のある参戦記です。

まず問題をざっと読み、Aは面倒臭そうなので一旦飛ばしました。Bに行き、Bの問題を読み終えて、少々あやふやながらも組んで、提出しました。あやふやですが、現在の進行状況をバーで表したとき,どうなりますか,というような問題。ここまで10分少々。

続いてCの問題に行き、これを読んで、解けそうだったので解いていきます。初めは少々面倒な操作をしていたのですが、馬鹿な操作をなくし、枝刈りを施して、3度の誤提出の後に無事Pretestを通過。ここまでで約40分かかっています。C問題は円上に等間隔に取られた点に対し、「使っていい点」と「使ってはいけない点」を入力させ、この内「使っていい点」だけを用いて三角形以上の正多角形が作れるかどうか判定せよ、という問題でした。単純に効率よく判定していけば、さして難しい問題ではありませんでした。

D,Eをざっと読み、Dの方がEより難しそうだと思いつつも、どちらも実装が面倒そうだったのでAの実装に取り掛かります。strlen関数を使えばさして難しくない問題だったので、少々デバッグをして完了。苦労なく仕上がりました。これで50分強。後1時間10分。

この後、D,Eを見比べて
D:なんとなくアルゴリズムは見えているような気がする。
E:アルゴリズムは明確だけど、調べなければならず、実装している暇がないように思える。
という結論に至り、Dを解くことにしました。ここまでで1時間10分が経過していました。

約20分間、Dを書きますが、20分かけて書いたのがようやく初期化・入力処理だけでした。この後15分ぐらいアルゴリズムを正確に実装する方法を考えたのですが、確信が持てず、ソースをロックしてハックに移行。Cのハックを始めたのですが、特に見つからないまま終了。

問題はこちら
結果、Bは誤りだったようで、A,CがAcceptedであり、205/1103位でした。上位20%層に入っていますから、まだまだ捨てたものではないのかもしれません。もっと精進していきたいものですね。
以下、いつもどおり、答案を載せておきます。Bは誤っているそうですが、まだ検討していません。誤りを出す入力を見つけたら教えていただければ幸いです。


A:strlen関数を用いれば一発ですが、fgetsは終端の改行まで読んでしまう点に注意します。

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

int main(void){
  char str[128],c;
  int n,m;
  scanf("%d%c",&n,&c);
  while(n>0){
    fgets(str,sizeof(str)/sizeof(char),stdin);
    m=strlen(str);
    if(m>11){
      printf("%c%d%c\n",str[0],m-3,str[m-2]);
    }else{
      printf("%s",str);
    }
    n--;
  }
  return 0;
}

B:計算間違いか誤差か…検討していませんが、もう少し考えてみたいところです。
#include<stdio.h>

int main(void){
  int i,j,k,n,m,t;
  scanf("%d %d %d",&n,&k,&t);
  m=n*k*t/100;
  for(i=1;i*k<=m;i++) printf("%d ",k);
  printf("%d ",m%k);
  for(j=0;j<n-i;j++){
    printf("0");
    putchar((j==n-i-1)?'\n':' ');
  }
  return 0;
}

C:フラグのたて方をうまくやらないと失敗するようで、ここで引っかかって時間を食いました。
#include<stdio.h>
#include<stdlib.h>

int main(void){
  int n,*knights,i,j,k,flg;
  scanf("%d",&n);
  knights=(int *)calloc(n,sizeof(int));
  for(i=0;i<n;i++) scanf("%d",knights+i);
  for(i=1;i<=n/3;i++){//polygon num
    flg=0;
    if(n%i!=0){
      flg=1;
      continue;
    }
    for(j=0;j<i;j++){//begin from?
      flg=0;
      for(k=j;k<n;k+=i){
if(knights[k]==0){
 flg=1;
 break;
}
      }
      if(flg==0) break;
    }
    if(flg==0) break;
  }
  if(flg==0){
      puts("YES");
    }else{
      puts("NO");
    }
  free(knights);
  return 0;
}

0 件のコメント: