2011年4月21日木曜日

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

久しぶりにきちんと参加した大会になりました。

サーバー落ちのためか、開始時間が15分遅れてのスタート。直前まで知らなくて、00時丁度につなげずに焦りました。

問題を俯瞰すると遅くなることが分かってきたので、とりあえず目の前のAをやりました。簡単に見えるけど、時間制限に引っかからないかな?と思って実装。単純には、入力されるa,b(a<b)に対し、aとbが連続素数になっているかどうかを判定せよ、という問題です。解き終えるのに10分。後から考えるともう少し早い実装があったのが悔しい限りですが、特殊化なのでやらなくてもよかったかもしれません。

ついでB。ざっと読んで、なんとなく「時刻が入力されるとき、時針・分針が12:00から何度回ったか出力すればいいのかな?」と思い、それを作って提出。…一発でacceptedでした。正直怖かったです。ここまでで合計17分。快調です。

Cは面倒そうなのでD。これも意外に解けるように感じた問題でした。入力される範囲に対して、特定の二次方程式が解を持つ範囲の割合を求める問題です。数学が苦手な人には難しい問題なのかもしれませんが、p-q平面を考えれば後は高等学校レベルの解析幾何・一次関数の問題でした。とはいえ、単純ではないかもしれません。これを解いて合計34分。残りは面倒そうなものばかりが残ってしまいました。

Cの方が簡単そうだったのでCの実装を試みますが、なかなかうまくいかない。うまく言った頃には残り5分でした。全探索でも意外と回数は少ないのですが、どこかで計算を間違えたのか、はたまた読み違えたか、acceptedがでません。そのまま時間終了。

最終結果はDがとある初歩的ミスにより失敗だったので
1412点、253位
でした。

問題はこちら

ではいつもどおり、解答ソースコードを載せておきます。

A:簡単でしたが無事に正解でした。でも、素数判定関数primeはもう少し簡単に出来た気がします。

#include<stdio.h>

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

int main(void){
  int a,b,i;
  scanf("%d %d",&a,&b);
  if(prime(a)){
    puts("NO");
    return 0;
  }
  if(prime(b)){
    puts("NO");
    return 0;
  }
  for(i=(a==2)?3:a+2;i<b;i+=2){
    if(!prime(i)){
      puts("NO");
      return 0;
    }
  }
  puts("YES");
  return 0;
}


B:無事に正解をいただきましたが、やけに簡単だったいうのが正直な意見です。パソコン甲子園の過去問題を始め、いろいろな問題を解いた経験でしょうか?

#include<stdio.h>
int main(void){
  int hh,mm;
  double degh,degm;
  scanf("%d:%d",&hh,&mm);
  degh=hh%12*30+0.5*mm;
  degm=6*mm;
  printf("%f %f\n",degh,degm);
  return 0;
}


C:全探索で組んでいますが、もっと良い解法があったような気がします。そもそも解けていないという方が良いソースです。

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

int search(char *str){
  if(!strncmp(str,"An",2)){
    return 0;
  }else if(!strncmp(str,"Ch",2)){
    return 1;
  }else if(!strncmp(str,"Cl",2)){
    return 2;
  }else if(!strncmp(str,"Tr",2)){
    return 3;
  }else if(!strncmp(str,"Dr",2)){
    return 4;
  }else if(!strncmp(str,"Sn",2)){
    return 5;
  }else if(!strncmp(str,"He",2)){
    return 6;
  }
  return 7;
}

int intpow(int a,int b){
  int prod;
  for(prod=1;b>0;b--) prod*=a;
  return prod;
}

int main(void){
  short like[7][7];
  short group[7];
  short num[3];
  int exp[3],gexp[3];
  int i,j,k,l,m,n;
  int sumlike,difexp;
  int s=0,d;
  char *from,*to,tmp;

  from=(char *)calloc(16,sizeof(char));
  to=(char *)calloc(16,sizeof(char));

  for(i=0;i<7;i++) for(j=0;j<7;j++) like[i][j]=0;

  scanf("%d%c",&n,&tmp);
  for(k=0;k<n;k++){
    scanf("%s likes %s",from,to);
    i=search(from);
    j=search(to);
    like[i][j]=1;
  }
  free(to);
  free(from);

  scanf("%d %d %d",exp,exp+1,exp+2);
  d=MAX(MAX(exp[0],exp[1]),exp[2])-MIN(MIN(exp[0],exp[1]),exp[2])/7;

  for(i=5;i<=2185;i++){
    num[0]=num[1]=num[2]=0;
    for(j=0;j<7;j++){
      m=i/intpow(3,j)%3;
      group[j]=m;
      num[m]++;
    }
    if(num[0]==0 || num[1]==0 || num[2]==0) continue;
    for(j=0;j<3;j++) gexp[j]=exp[j]/num[j];
    difexp=MAX(MAX(gexp[0],gexp[1]),gexp[2])-MIN(MIN(gexp[0],gexp[1]),gexp[2]);
    sumlike=0;
    for(j=0;j<7;j++){
      for(k=0;k<7;k++){
        if(group[j]==group[k]) sumlike+=like[j][k];
      }
    }
    if((d>difexp && s==sumlike) || s<sumlike){
      s=sumlike;
      d=difexp;
    }
  }
  printf("%d %d\n",d,s);
  return 0;
}


D:上記では快調に解いたのですが、final testで引っかかってしまいました。その理由は「出力桁数の違い」、初歩的ミスに泣けてきます。

#include<stdio.h>
int main(void){
  int a,b,n;
  int i,j,k;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d %d",&a,&b);
    if(4*b>a){
      printf("%f\n",1-(2*b-a*0.25)/(4*b));
    }else{
      printf("%f\n",1-(double)b/a);
    }
  }
  return 0;
}

2 件のコメント:

Volcanologue さんのコメント...

実装までの速度も重要だから,primeは私もこう書くだろうと思う.
私なら,こういう条件でなければ,素数表をFortranかなにかで作っておいて,比較するのだけれど,この問題では time & performance でこれでいいと思うのですが.

達哉ん/Tatuyan さんのコメント...

>Volcanologue さん
ありがとうございます。
そうですね、時間と効率を考えたらこうして使い回すほうが早いですよね。
まぁ、後からの反省なので、気にせず楽しみたいと思っています。