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

大変良い出来でした。今までで最高の出来でした。

開始した後、10分でProblem Aをaccepted。非常に単純な問題でした。

Bにとりかかります。19,21分にwrong answer。問題の解釈違いに気づいて直して22分でacceptedです。

Problem C。フォルダの選択方法に関する問題です。普段遊んでいる内容だったので、楽しく組みましたが、2度wrong answer。一つミスをしていることに気づき、直して42分にaccepted.

Problem Dが解けたのが、今回の幸運でした。問題を読んだ時、貪欲法であるように思い、迷いながらも組んでみました。すると、驚いたことに1回でaccepted(1:18)。ここでEに移りますが、解けずに終わりました。

問題はこちら。3816点、8位/1070人と好成績でした。うれしくてお祝いしてしまったぐらいです。また、青にランクアップしました。

A.読み込んだ文字列の比較を行うだけです。

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

int main(void){
  char str[81],num[10][11],sub[11];
  int i,j,k;
  scanf("%s",str);
  for(i=0;i<10;i++) scanf("%s",num[i]);
  for(i=0;i<8;i++){
    for(j=0;j<10;j++) sub[j]=str[j+10*i];
    sub[11]='\0';
    for(j=0;j<10;j++){
      if(strncmp(sub,num[j],10)==0){
printf("%d",j);
break;
      }
    }
  }
  putchar('\n');
  return 0;
}

   
B.配列を使うと、調べるのが簡単になります。

#include<stdio.h>

int main(void){
  int in1,in2,people[5];
  int m,n,i,flg=0;
  for(i=0;i<5;i++) people[i]=0;
  scanf("%d",&m);
  for(i=0;i<m;i++){
    scanf("%d %d",&in1,&in2);
    people[in1-1]++;
    people[in2-1]++;
  }
  for(i=0;i<5;i++){
    if(people[i]!=2){
      puts("WIN");
      flg=1;
      break;
    }
  }
  if(flg!=1) puts("FAIL");
  return 0;
}

C.漏れがないように場合分けして書けば解けます。

#include<stdio.h>
typedef unsigned int u_int;
int main(void){
  u_int m,n,a,b,a_pos,b_pos,a_line,b_line,k;
  scanf("%u %u %u %u",&m,&n,&a,&b);
  a_pos=(a-1)%n+1;
  b_pos=(b-1)%n+1;
  a_line=(a-1)/n;
  b_line=(b-1)/n;
  if(b==m) b_pos=n;
  if(a_line==b_line){
    k=1;
  }else if(a_pos==1 && b_pos==n){
    k=1;
  }else if(a_pos==1 || b_pos==n){
    k=2;
  }else if(b_pos+1==a_pos){
    k=2;
  }else if(a_line+1==b_line){
    k=2;
  }else{
    k=3;
  }
  printf("%d\n",k);
  return 0;
}

D.典型的な貪欲法の問題です。

#include<stdio.h>

#define MIN(x,y) ((x<y)?(x):(y))

int main(void){
  int n,m,w;
  double milk[50];
  double cup[50];
  double goals,pour;
  int i,j,k,now,flg;
 
  scanf("%d %d %d",&n,&w,&m);
  for(i=0;i<n;i++) milk[i]=w;
  for(i=0;i<m;i++) cup[i]=0;
  goals=(double)w*(double)n/(double)m;
  now=0;
  flg=0;
  for(i=0;i<m;i++){
    pour=MIN(goals-cup[i],milk[now]);
    cup[i]+=pour;
    milk[now]-=pour;
    if(milk[now]<1E-6){
      now++;
      flg=0;
    }else{
      flg++;
    }
    if(flg==2){
      puts("NO");
      return 0;
    }
    if(cup[i]<goals-(1E-6)){
      i--;
    }
  }

  for(i=0;i<n;i++) milk[i]=w;
  for(i=0;i<m;i++) cup[i]=0;
  now=0;
  puts("YES");
  for(i=0;i<m;i++){
    pour=MIN(goals-cup[i],milk[now]);
    cup[i]+=pour;
    milk[now]-=pour;
    printf("%d %.6f",now+1,pour);
    if(milk[now]<1E-6) now++;
    if(cup[i]<goals-(1E-6)){
      putchar(' ');
      i--;
    }else{
      putchar('\n');
    }
  }

  return 0;
}