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

終了10時間後からUTPC2011があるので、そのプラクティスまで入れて3ラウンドの真ん中に位置するCodeforces Beta Round #72に参加してきました。なお、UTPC2011はちょこちょこ参加する感じですが、この参戦記は後日。

第1問、これは良問。3n/2を出力すれば良い、ということを予想して解答、accepted。ここまで8分、好調。

第2問、いろいろ考えるが、ソートするとダメそうなので、前から愚直に「これを初項とする、条件を満たす部分列は…」と線形探索。後から考えれば、これでは当然遅すぎて、同じ数字からなる連続部分列の長さをnとして、n(n+1)/2がその部分から取れる数。愚かなミスです。当然TLEになるのですが、Pretest acceptedで油断しました。ここまで28分。

第3問、バイアスロンの的あて問題。これも第2問と全く同じ罠にはまります。これで50分です。

第4問、これはキューを愚直に弄るとアウトとなるとおもい、いろいろ変更してみますが、なんだかんだでキューを弄るのと変わらない時間がかかるプログラム。その上、痛恨のミスで、最後までacceptedが取れませんでした。

結果はaのみ正解で504/1042位、484点でした。問題はこちら

A:これは無事でした。

#include<stdio.h>

int main(void){
  unsigned int n;
  scanf("%u",&n);
  printf("%u\n",n/2*3);
  return 0;
}



B:上の「愚直な」プログラム。今回はリニアサーチに取り憑かれた？

#include<stdio.h>
#include<stdlib.h>
int main(void){
  int *array,i,j,k,n,count=0,same;
  scanf("%d",&n);
  array=(int *)calloc(n,sizeof(int));
  for(i=0;i<n;i++) scanf("%d",array+i);
  for(i=0;i<n;i++){
    same=0;
    for(j=1;j<n-i;j++){
      if(*(array+i)==*(array+i+j)){
same++;
continue;
      }else break;
    }
    count+=same+1;
  }
  printf("%d\n",count);
  free(array);
  return 0;
}


C:同じく。

#include<stdio.h>
#include<stdlib.h>
typedef struct{
  int x;
  int r;
  int first;
} targets;

typedef struct{
  int x;
  int y;
} points;

typedef unsigned int u_int;

int hit(targets target,points p){
  int tmp;
  tmp=abs(target.x-p.x);
  if(tmp*tmp+p.y*p.y<=target.r*target.r)return 1;
  return 0;
}

int main(void){
  u_int m,n;
  u_int count=0,two;
  int i,j,k;
  targets *target;
  points *shot;
  scanf("%u",&n);
  target=(targets *)calloc(n,sizeof(targets));
  for(i=0;i<n;i++){
    scanf("%d %d",&((target+i)->x),&((target+i)->r));
    (target+i)->first=-1;
  }
  scanf("%u",&m);
  shot=(points *)calloc(m,sizeof(points));
  for(i=0;i<m;i++){
    scanf("%d %d",&((shot+i)->x),&((shot+i)->y));
  }
  for(i=0;i<m;i++){
    two=0;
    for(j=0;j<n;j++){
      if(hit(*(target+j),*(shot+i))==0) continue;
      if((target+j)->first==-1){
(target+j)->first=i+1;
count++;
      }
      two++;
      if(two==2) break;
    }
  }
  printf("%d\n",count);
  for(i=0;i<n;i++){
    printf("%d",(target+i)->first);
    putchar(i==n-1?'\n':' ');
  }
  free(target);
  free(shot);
  return 0;
}


D:さらに同じく。

#include<stdio.h>
#include<stdlib.h>
int main(void){
  unsigned long long int k;
  unsigned int n,las;
  unsigned int *a;
  unsigned int i,j,flg=0;
  //scanf("%u %I64u",&n,&k);
  scanf("%u %llu",&n,&k);
  a=(unsigned int*)calloc(n,sizeof(unsigned int));
  for(i=0;i<n;i++) scanf("%u",a+i);
  las=n;

  while(k>=las){
    for(i=0;i<n;i++){
      if(*(a+i)==0) continue;
      (*(a+i))--;
      if(*(a+i)==0) las--;
      k--;
    }
    if(las==0){
        printf("-1\n");
        free(a);
        return 0;
    }
  }

  if(las==0){
    printf("-1\n");
    free(a);
    return 0;
  }

  if(k==0) flg=1;

  for(i=0;k!=0&&i<n;i++){
    if(*(a+i)==0) continue;
    (*(a+i))--;
    k--;
    if(*(a+i)==0) las--;
    if(las==0){
        printf("-1\n");
        free(a);
        return 0;
    }
    if(k==0) break;
  }

  for(j=(flg==1)?0:i+1;j<n;j++){
    if(*(a+j)==0) continue;
    printf("%u",j+1);
    *(a+j)=0;
    las--;
    if(las==0){
      putchar('\n');
      free(a);
      return 0;
    }
    putchar(' ');
  }

  for(j=0;j<=i&&flg!=1;j++){
    if(*(a+j)==0) continue;
    printf("%u",j+1);
    *(a+j)=0;
    las--;
    if(las==0){
      putchar('\n');
      free(a);
      return 0;
    }
    putchar(' ');
  }

  free(a);
  return 0;
}