KUPC2011(プラクティス含む) 参戦記

※ This contest is only Japanese. So, in this blog, I write report only Japanese.
※ 問題文が日本語限定なので、こちらは日本語のみといたします。

KUPC2011に参加してきました。KUPCとは、京都大学プログラミングコンテストのことで、私の知る限りは、今年からの開催かと思います。主催者の何人かと話したことがありますので、参加せねばならないと参加しました。

まず、前日のプラクティスです。ひとまず問題をざっと読み、とく順番をBCDAと決めます。インタラクティブ系問題は初めてなので、どのようになるかが楽しみでした。

プラクティスはいずれも、テストケースが小さかったり問題自体が簡単だったりして、苦労なく解くことが出来る問題ばかりでした。プラクティスとして妥当だったのではないかと思います。UTPCの「ツンデレ」や「にゃー」のような問題がないのが、安心したのもあり、少し残念でもありました。でも、にゃーはもう一度解きたいです。

当日は別の用事と並行しての参加でした。
まず、13時30分頃、ようやくパソコンを叩く暇ができたので、Aを解き始めます。

A問題は実装するだけの問題です。K,U,P,Cの各々の数を数え、そのうち最も少ないものの数を出力する、というだけで解くことができます。

続いてB問題。読んだ瞬間に最短路問題だな、ということで、漸化式を立てて計算しました。いわゆるDPですね。これも苦労なく通しました。

次にしりとりのC問題です。これはつまらないミスを多発して、数回みすりましたが、最終的には解くことができました。インタラクティブの面白い問題でした。

ここで、用事が入ったので一旦中断し、1時間たってから戻ってきます。残り時間は2時間になっていました。

Dは難しそうだったので、Eをやります。が、Eの妥当な解法が思いつきません。単純に探索するだけではメモリも時間も厳しい問題です。どうすれば解くことが出来るのか、解説を楽しみにしたいと思います。

結局A,B,Cの3問で終わりまして、順位は84位でした。問題はこちら。プラクティスは17位で、問題はこちら。

友人とやる予定の検討会の資料に書いた感想を抜粋します。

•問題難易度は日本の大学主催の問題としては妥当〜難ぐらい。一般的には、Codeforces の無差別級〜Div.1 程度では。
• 5 時間 10 問という量は妥当。
• ある (既製の) プログラムに対して応答を答える問題は IOI 以外では珍しい。
• 解けた問題数と時間ペナルティによる採点なので、問題難易度に対しての旨味がない。配点に差をつけたほうが面白いように感じる。
• 時間制限 1 秒、メモリ制限 64MB は厳しい。(時間は Codeforces 標準の半分、メモリは同 1/4 である。)
• 全問正解者/最終問題正解者 0 というのはやり過ぎの感がある。
•問題難易度の分布が指数関数的な気がする。
•でも全体としては素晴らしいコンテスト。
運営者の皆様、ありがとうございました。またこんな大会をお願いします。


A

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

int main(void){
  int count[4];
  int i,j,k,min;
  char str[512];
  memset(count,0,sizeof(count));
  scanf("%s",str);
  k=strlen(str);
  for(i=0;i<k;i++){
    switch(str[i]){
    case 'K':
      count[0]++;
      break;
    case 'U':
      count[1]++;
      break;
    case 'P':
      count[2]++;
      break;
    case 'C':
      count[3]++;
      break;
    }
  }
  min=count[0];
  for(i=1;i<=3;i++) if(count[i]<min) min=count[i];
  printf("%d\n",min);
  return 0;
}


B

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

int main(void){
  short map[50][50];
  int mins[50][50];
  int i,j,l,m;
  int h,w;
  scanf("%d %d",&h,&w);
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      scanf("%1hd",&map[i][j]);
    }
  }
  mins[0][0]=map[0][0];
  for(i=1;i<w;i++) mins[0][i]=map[0][i]+mins[0][i-1];
  for(i=1;i<h;i++){
    mins[i][0]=map[i][0]+mins[i-1][0];
    for(j=1;j<w;j++){
      mins[i][j]=map[i][j]+MIN(mins[i-1][j],mins[i][j-1]);
    }
  }
  printf("%d\n",mins[h-1][w-1]);
  return 0;
}



C

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

int getnum(char c);

int main(void){
  short flg[26];
  char chara='a',count[2];
  char str[11],ai[10];
  int i,j,k,l,m;
 
  count[0]=count[1]=0;
  memset(flg,0,sizeof(flg));
  printf("?a\n");
  fflush(stdout);
  for(i=1;i<50;i++){
    scanf("%s%*c",ai);
    if(ai[0]!=chara){
      printf("!OUT\n");
      fflush(stdout);
      break;
    }
    if(flg[getnum(ai[1])]!=0){
      printf("!OUT\n");
      fflush(stdout);
      break;
    }
    if(strlen(ai)==1 && ai[0]=='a'){
      printf("!OUT\n");
      fflush(stdout);
      break;
    }
    flg[getnum(ai[1])]=1;
    if(flg[0]==0 && ai[1]=='a'){
      printf("?aa\n");
      flg[0]=1;
      fflush(stdout);
    }else{
      count[0]++;
      if(count[0]>=26){
count[0]%=26;
count[1]++;
      }
      printf("?%c%c%c%c\n",ai[1],'a'+count[0],'a'+count[1],chara);
      fflush(stdout);
    }
  }
  return 0;
}

int getnum(char c){
  const char *alpha="abcdefghijklmnopqrstuvwxyz\0";
  return strchr(alpha,c)-alpha;
}


E(Wrong)

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

int main(void){
  char primelist[1000001];
  int list[1000010];
  long long int a;
  long long int i,j,k,l,m;
  int b,count;

  scanf("%lld %d",&a,&b);
  for(i=1;4*(i*(i+1))<a+b;i++){
    if(primelist[i]!=0) continue;
    k=2*i+1;
    for(j=(k*k-1)/2;j*j<=a+b;j+=k) primelist[j]=1;
  }

  for(j=(((a-b)%2==0)?-b:-b+1);j<=b;j+=2){
      for(l=0,m=a+j;m%2==0;l++) m/=2;
      list[j+b]=l;
  }
   
  for(i=1;4*(i*(i+1))<a+b;i++){
    if(primelist[i]!=0) continue;
    k=2*i+1;
    for(j=-b+k-((a-b-1)%k+1);j<=b;j+=k){
      if(list[j+b]<0) continue;
      for(l=0,m=a+j;m%k==0;l++) m/=k;
      //if(l==0) continue;
      if(l<=list[j+b] || list[j+b]==0) list[j+b]=l;
      else list[j+b]=-1;
    }
  }
 
  for(i=-b;i<=b;i++) count+=(list[i+b]!=-1);
  printf("%d\n",count);
  return 0;
}
 


Practice-A

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

void subcopy(char dist[],char src[],int from,int to);

int main(void){
  char str[10][51];
  char substr[51];
  int m,n,i,j,k,flg;
  scanf("%d %d",&n,&m);
  for(i=0;i<n;i++) scanf("%s%*c",str[i]);
  for(i=m;i>0;i--){
    for(j=0;j<=m-i;j++){
      subcopy(substr,str[0],j,j+i-1);
      flg=1;
      for(k=1;k<n;k++){
if(strstr(str[k],substr)==NULL) flg=0;
if(flg==0) break;
      }
      if(flg==1) break;
    }
    if(flg==1) break;
  }
  printf("%d\n",i);
  return 0;
}

void subcopy(char dist[],char src[],int from,int to){
  int i;
  for(i=from;i<=to;i++) dist[i-from]=src[i];
  dist[to-from+1]='\0';
}


Practice-B

#include<stdio.h>
int main(void){
  unsigned long long int sum=0,n,tmp;
  scanf("%llu",&n);
  while(n--){
    scanf("%llu",&tmp);
    sum+=tmp;
  }
  printf("%llu\n",sum);
  return 0;
}



Practice-C

#include<stdio.h>

int main(void){
  int a;
  printf("?number\n");
  fflush(stdout);
  scanf("%d", &a);
  printf("!%d\n",a);
  fflush(stdout);
  fflush(stdout);
  return 0;
}


Practice-D

#include<stdio.h>

#define MAX ((unsigned int)1<<(unsigned int)30)

int main(void){
  unsigned int num,ans,i;
  num=MAX/2;
  for(i=0;i<32;i++){
    printf("?%d\n",num);
    fflush(stdout);
    scanf("%d", &ans);
    if(ans==0){
      printf("!%d\n",num);
      fflush(stdout);
      break;
    }else if(ans==1){
      num+=MAX/(2<<(i+1));
    }else{
      num-=MAX/(2<<(i+1));
    }
  }
  return 0;
}