Codeforces Beta Round #67(Div.2) 中途半端参戦記

開始前から疲れているような気がしたので、やる気がなくなった段階でやめようとCodeforces #67に中途半端に参加しました。問題はこちら

ざっと見て、問題Aは簡単そうなので解き始める。要するに0を抜けばいい、ということで文字列操作と数字への変換を使って18分、完了。

その後、Bは面倒臭そうなので飛ばして、Cへ。これもそれほど苦労しないだろう、とEuclidの互除法と線形探索で解く。

その後、Bを解いて提出する直前、Cがハックされる。時間制限をオーバーしているということだったので、枝狩りをして再提出。

Bを提出したけれどもミス、問題にソート等の条件があることを確認して、疲れてきたのでここでGive up!(その後、Cが再度ハックされましたが、作り直そうとは思いませんでした)。

今回は途中退室ですので、事実上Aだけしか解けませんでした。疲れているときは素直にねるに限りますね。



いつもどおりソースを乗っけておきます。
A:これは解きました。

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

int exzero(int a){
  char tmp[16],put[3],num[16];
  int i,j,k,n;

  for(i=0,j=0;i<=9;i++){
    if(a%10!=0){
      sprintf(put,"%d",a%10);
      tmp[j]=put[0];
      j++;
    }
    a/=10;
    if(a==0) break;
  }
  tmp[j]='\0';
  for(i=0;i<j;i++) num[i]=tmp[j-i-1];
  num[i]='\0';
  a=atoi(num);
  return a;
}

int main(void){
  int a,b,c;
  scanf("%d",&a);
  scanf("%d",&b);
  c=a+b;
  a=exzero(a);
  b=exzero(b);
  c=exzero(c);
  if(a+b==c){
    puts("YES");
  }else{
    puts("NO");
  }
  return 0;
}

B:ソートを実装していません。

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

int main(void){
  char name[200][12];
  char tmp[1024],cc;
  char *srch;
  int now=1,i,j,k,n,flg;
  fgets(name[0],sizeof(name[0])/sizeof(char),stdin);
  name[0][strlen(name[0])-1]='\0';
  scanf("%d%c",&n,&cc);
  for(i=0;i<n;i++){
    fgets(tmp,sizeof(tmp)/sizeof(char),stdin);
    srch=strtok(tmp," ");
    for(j=0,flg=0;j<now;j++){
      if(strcmp(name[j],srch)==0){
flg=1;
break;
      }
    }
    if(flg==0){
      strcpy(name[now],srch);
      now++;
    }
    srch=strtok(tmp," ");
    if(strcmp(srch,"posted")==0){
      srch=strtok(tmp," ");
      srch=strtok(tmp,"'");
    }else if(strcmp(srch,"commented")){
      srch=strtok(tmp," ");
      srch=strtok(tmp,"'");
    }else{
      srch=strtok(tmp,"'");
    }
    for(j=0,flg=0;j<now;j++){
      if(strcmp(name[j],srch)==0){
flg=1;
break;
      }
    }
    if(flg==0){
      strcpy(name[now],srch);
      now++;
    }
  }
  for(i=1;i<now;i++){
    puts(name[i]);
  }
  return 0;
}

C:時間制限オーバーでした。

#include<stdio.h>

int euclid(int a,int b){
  if(b==0) return a;
  else return euclid(b,a%b);
}

int main(void){
  int a,b,g,c;
  int l,m,n,flg=0;
  int i,j;
  scanf("%d %d",&a,&b);
  scanf("%d",&n);
  g=euclid(a,b);
  for(i=0;i<n;i++){
    scanf("%d %d",&l,&m);
    flg=0;
    if(g<l){
      printf("-1\n");
      continue;
    }
    for(j=((m>g)?g:m);j>=l;j--){
      if(g%j!=0) continue;
      flg=1;
      printf("%d\n",j);
      break;
    }
    if(flg==0){
      printf("-1\n");
    }
  }
  return 0;
}