Codeforces Beta Round #83 & #86 (Div.2) 参戦記

まだ書いていなかったので、#83と合わせてお送りします。

<Codeforces Beta Round #83 (Div.2)>
疲れていまして、1問しか解けませんでした。
Aを00:04に提出して、それっきりです。

B: もしも最大値が他の値の2倍より小さければYESと出せばいいのでは？と思いましたが、間違っていたようで、System testで落とされました。

その後、あまりに眠かったので、寝てしまいました。
得点は492, 順位は465/1179でした。

<Codeforces Beta Round #86 (Div.2)>
スランプに陥っているような気がしてなりません。

A:一読しただけではわからなかったのですが、再読して平方数の判定だけだと分からいました。00:04に提出して、これだけが正解でした。

B: 試してみて、提出まで漕ぎ着けた後、自分の勘違いに気が付きました。面倒だったので諦めました。どう勘違いしたか知りたい方はソースを見てみてください。

C:解いたのですが、
"A sentence is either exactly one valid language word or exactly one statement.".
を見逃していました。コンテストの後、これを確認して再度解いてACを得ました。

E: フェルマーの4N+1定理と思ったのですが、私のソースではシンプルすぎてTLEでした。区間篩など使う必要があるのではないでしょうか。時間があれば試してみたいところです。

得点は492,順位は377/1337, レーティングは1418->1452でした。
少々難しいコンテストだったのでしょうか？


[#83 A(Correct)]

#include<stdio.h>

int main(void){
  int hh,mm;
  scanf("%d:%d",&hh,&mm);
  do{
    mm++;
    if(mm==60){
      mm=0;
      hh++;
    }
    if(hh==24) hh=0;
  }while(!(mm/10==hh%10 && hh/10==mm%10));
  printf("%02d:%02d\n",hh,mm);
  return 0;
}


[#83 B(Wrong)]

#include<stdio.h>
#include<stdlib.h>
#define MAX(x,y) (((x)<(y))?(y):(x))

int main(void){
  unsigned int *data;
  unsigned int n,max=0;
  unsigned int i,j,k;

  scanf("%u",&n);
  data=(unsigned int *)calloc(n,sizeof(unsigned int));
  for(i=0;i<n;i++) scanf("%u",data+i);
  for(i=0;i<n;i++) max=MAX(max,*(data+i));
  for(i=0;i<n;i++){
    if(max<=*(data+i)) continue;
    if(max<2*(*(data+i))){
      puts("YES");
      return 0;
    }
  }
  puts("NO");
  free(data);
  return 0;
}


[#86 A(Correct)]

#include<stdio.h>

typedef unsigned int u_int;

int main(void){
  u_int i,n,k;
  scanf("%u",&k);
  scanf("%u",&n);
  for(i=0;n!=1;i++,n/=k){
    if(n%k!=0){
      puts("NO");
      return 0;
    }
  }
  printf("YES\n%u\n",i-1);
  return 0;
}



[#86 B(Wrong)]

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

typedef struct {
  char name[11];
  int group;
} mem;

void ssort(mem member[],int size);

int main(void){
  mem member[16];
  char name[2][11];
  int n,m,i,j,k,g=1;
  int tmpg,num[2];
  scanf("%u %u",&n,&m);
  for(i=0;i<n;i++) scanf("%s%*c",member[i].name);
  for(i=0;i<n;i++) member[i].group=0;
  ssort(member,n);
  for(i=0;i<m;i++){
    scanf("%s %s%*c",name[0],name[1]);
    for(j=0;j<n;j++){
      if(strcmp(name[0],member[j].name)==0) num[0]=j;
      else if(strcmp(name[1],member[j].name)==0) num[1]=j;
    }
    if(member[num[0]].group==0 && member[num[1]].group==0){
      member[num[0]].group=g;
      member[num[1]].group=g;
      g++;
    }else if(member[num[0]].group==0){
      member[num[0]].group=member[num[1]].group;
    }else if(member[num[1]].group==0){
      member[num[1]].group=member[num[0]].group;
    }else{
      tmpg=member[num[1]].group;
      for(j=0;j<n;j++){
if(member[j].group==tmpg) member[j].group=member[num[0]].group;
      }
    }
  }
  g=0;
  for(i=0;i<n;i++){
    if(member[i].group==0){
      g++;
    }else if(member[i].group>0){
      g++;
      for(j=i+1;j<n;j++){
if(member[j].group==member[i].group) member[j].group=-1;
      }
    }
  }
  printf("%d\n",g);
  for(i=0;i<n;i++) if(member[i].group>=0) puts(member[i].name);
  return 0;
}

void ssort(mem member[],int size){
  int i,j,place;
  mem tmp;
  for(i=0;i<size;i++){
    place=i;
    for(j=i+1;j<size;j++) if(strcmp(member[place].name,member[j].name)>0) place=j;
    tmp=member[i];
    member[i]=member[place];
    member[place]=tmp;
  }
}

[#86 C(Correct)]

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

int types(char *str);

int main(void){
  char str[100002],*p;
  int gender,now,tmp;
  int flg=0,inwhile=0;

  fgets(str,sizeof(str),stdin);
  str[strlen(str)-1]='\0';
  p=strtok(str," ");
  tmp=types(p);
  if(tmp==0){
    puts("NO");
    return 0;
  }
  gender=tmp%2;
  now=(tmp-1)/2;
  if(now==1) flg=1;
  while(1){
    p=strtok(NULL," ");
    if(p==NULL) break;
    inwhile=1;
    tmp=types(p);
    if(tmp==0 || tmp%2!=gender || now>(tmp-1)/2 || (now==1 && (tmp-1)/2==1)){
      puts("NO");
      return 0;
    }
    now=(tmp-1)/2;
    if(now==1) flg=1;
  }
  if(flg==1 || inwhile==0) puts("YES");
  else puts("NO");
  return 0;
}

int types(char *str){
  int len;
  len=strlen(str);
  if(len<3) return 0;
  if(strcmp(str+len-4,"lios")==0) return 1;
  if(strcmp(str+len-5,"liala")==0) return 2;
  if(strcmp(str+len-3,"etr")==0) return 3;
  if(strcmp(str+len-4,"etra")==0) return 4;
  if(strcmp(str+len-6,"initis")==0) return 5;
  if(strcmp(str+len-6,"inites")==0) return 6;
  return 0;
}


[#86 E(Time Limit Exceeded)]

#include<stdio.h>

int prime(int p){
  int i;
  if(p==1) return 0;
  for(i=3;i*i<=p;i+=2) if(p%i==0) return 0;
  return 1;
}

int main(void){
  int l,r,i,j,k,count=0;
  scanf("%d %d",&l,&r);
  if(l<=2 && r>=2) count++;
  switch(l%4){
  case 0:
    l++;
    break;
  case 2:
    l+=3;
    break;
  case 3:
    l+=2;
    break;
  }
  for(i=l;i<=r;i+=4) if(prime(i)) count++;
  printf("%d\n",count);
  return 0;
}