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

問題文が短く、大変良いコンテストであったと思います。また、今回、全ての問題を提出するという初の経験をさせてもらいました。結局ケアレスミスで2問しか正解できなかったのですが…。

A: strcmpでOKな問題です。0:07にAccepted.

B: ちょっと考えれば単純な条件がでます。0:17にAccepted.

C: 0:39に提出しましたが、そこでは y<nである可能性を見逃していました。ハックされ、気づくことなく、終わってから他の人のソースを見て気づきました。アルゴリズムは正しいようです。

D: 0:56に提出しましたが、intにしておけばいいものをshortにしていたためシステムテストで落ちました。勿論、intにすれば通りましたから、アルゴリズムは間違いなかったようです。

E:提出はしたものの、正しくはありません。

問題はこちら.
結果は:1418,442位/1273人. Rateは1419->1418.
CやDのアルゴリズムが知りたいなら、ソースを読んでください。

次の記事では、忘れていたCodeforces #83の参戦記を書きます。

[A]

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

int main(void){
  char str[2][128];
  int i;
  scanf("%s%*c",str[0]);
  scanf("%s%*c",str[1]);
  for(i=0;i<strlen(str[0]);i++) str[0][i]=tolower(str[0][i]);
  for(i=0;i<strlen(str[1]);i++) str[1][i]=tolower(str[1][i]);
  i=strcmp(str[0],str[1]);
  if(i<0) puts("-1");
  else if(i==0) puts("0");
  else puts("1");
  return 0;
}

[B]

#include<stdio.h>

int main(void){
  int n,x,y;
  scanf("%d %d %d",&n,&x,&y);
  if((x==n/2 || x==n/2+1)&&(y==n/2 || y==n/2+1)) puts("NO");
  else puts("YES");
  return 0;
}

[C](コンテスト後の正答ソース)

#include<stdio.h>

typedef unsigned long long int u_long;

int main(void){
  u_long x,y,n;
  u_long i,j,k;
  u_long sum=0;
  scanf("%I64u %I64u %I64u",&n,&x,&y);
  if(y<n){
    puts("-1");
    return 0;
  }
  sum=(y-n+1)*(y-n+1);
  sum+=(n-1);
  if(sum<x){
    puts("-1");
  }else{
    printf("%I64u\n",(y-n+1));
    for(i=1;i<n;i++) puts("1");
  }
  return 0;
}


[D](コンテスト後の正答ソース)

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

int main(void){
  unsigned int div[100000];
  unsigned int i,j,k,n,x,y,now,count;
 
  memset(div,0,sizeof(div));
  scanf("%u",&n);
  for(now=1;now<=n;now++){
    scanf("%u %u",&x,&y);
    count=0;
    for(i=0;(i+1)*(i+1)<=x;i++){
      if(x%(i+1)!=0) continue;
      j=x/(i+1)-1;
      if(div[i]==0 || div[i]<now-y) count++;
      div[i]=now;
      if(div[j]==0 || div[j]<now-y) count++;
      div[j]=now;
    }
    printf("%u\n",count);
  }
  return 0;
}


[E](コンテスト中の間違いソース)


#include<stdio.h>
#include<string.h>
#define MIN(n,m) (((n)<(m))?(n):(m))

int main(void){
  int n,m,board[40][40],i,j,k,out=0;
  scanf("%d %d",&n,&m);
  memset(board,0,sizeof(board));
  for(i=0;i<m;i++){
    for(j=0;j<n;j++){
      if(j!=0 && board[i][j-1]==0 && board[i][j]==0){
board[i][j]=2;
out++;
      }
      if(i!=0 && board[i-1][j]==0){
board[i][j]=2;
out++;
      }
      if(i==m-1 && j!=0 && j!=n-1 && board[i][j-1]==0 && board[i][j+1]==0){
board[i][j]=2;
out++;
      }
      if(board[i][j]==2){
if(j-1!=0) board[i][j-1]=1;
if(i-1!=0) board[i-1][j]=1;
if(i+1<m) board[i+1][j]=1;
if(j+1<n) board[i][j+1]=1;
      }
    }
  }
  printf("%d\n",n*m-out);
  return 0;
}