Codeforces Beta Round #71 参戦記

遅ればせながら恒例の。

とりあえずAを読む。今回は(div.2)でないのであまり解けないかな？と思いながらでしたが、読んでみると何のことはない、普通に解ける問題でした。10分。

ついでBを読みます。区画ごとに何が埋まっているか、あるいは不毛の土地かというのが決まる。この時、指定される区画は何が埋まっているか？という問題です。問題を読むのに苦労しつつも(英語苦手です)、なんとか読んでやってみる…Memory limit!
上限を読み違えていて、盤面全体をshortで用意してもMemory limitに引っかかることがわかりました。そこでアルゴリズムを変えることに。状態が4つしかないから2bitで1状態を表すビットフィールドを使おうかと思いましたが、面倒そうなので個数の処理に頼ることに。不毛の土地を配列に記録しておき、後は[入力された場所は何番目で、その間の不毛の土地は幾つか数える」方針にしました。それで解き終えて…実は、先の名残でshortを残していたのがあとで発覚するのですが、47分にPretestを通ります。

その後、文字列入力の問題はあまり好きではないので後回しにしてDに。Lights Outの友人のような気がしながら、あーでもないこーでもない…と考えます。これをひたすら考えて45分、ダメそうなのでCに戻ります。

Cを色々組んだのですが、組み終えた後に重大なよみ違いに気づき、もう直す時間もないやと諦めて、2問。実力鑑みるとこんなもんかな？

が、B問題で残していたshortがオーバーフローを起こして(実際はintかunsigned shortにすべきです)、最終テストで発覚。残念でした、また今度…ということで、正解したのはAだけでした。

Scoreは480で、620/1183位でした。


今回のコードはAと修正版Bです。

A:たいしたことのないゲームです。愚直に組めばいい。

#include<stdio.h>
#define u_int unsigned int

int main(void){
  u_int ten,hand;
  u_int i=0;
  scanf("%u %u",&hand,&ten);
  while(1){
    if(i%2==0){
      if(hand>=2 && ten>=2){
        hand-=2;
        ten-=2;
      }else if(hand==1 && ten>=12){
        hand-=1;
        ten-=12;
      }else if(hand==0&& ten>=22){
        ten-=22;
      }else{
        puts("Hanako");
        return 0;
      }
    }else{
      if(ten>=22){
        ten-=22;
      }else if(ten>=12 && hand>=1){
        ten-=12;
        hand--;
      }else if(ten>=2 && hand>=2){
        ten-=2;
        hand-=2;
      }else{
        puts("Ciel");
        return 0;
      }
    }
    ++i;
  }
  return 0;
}

B:間違いを修正して、acceptをとったversionです。

#include<stdio.h>
#include<stdlib.h>
#define u_int unsigned int
int main(void){
  u_int i,j,ini,inj;
  u_int n,m,k,t,now;
  u_int *waste[2];
  u_int kosu,nws;
  scanf("%u %u %u %u",&n,&m,&k,&t);
  for(i=0;i<2;i++) waste[i]=(u_int *)calloc(k,sizeof(u_int));
  for(i=0;i<k;i++) scanf("%u %u",waste[0]+i,waste[1]+i);
  for(i=0;i<t;i++){
    scanf("%u %u",&ini,&inj);
    kosu=(ini-1)*m+inj;
    nws=1;
    for(j=0;j<k;j++){
      if(*(waste[0]+j)<ini){
        nws++;
      }else if(*(waste[0]+j)==ini){
        if(*(waste[1]+j)<inj){
          nws++;
        }else if(*(waste[1]+j)==inj){
          nws=0;
          break;
        }
      }
    }
    if(nws==0){
      puts("Waste");
      continue;
    }
    kosu-=nws;
    kosu++;
    switch(kosu%3){
    case 0:
      puts("Grapes");
      break;
    case 1:
      puts("Carrots");
      break;
    case 2:
      puts("Kiwis");
      break;
    }
  }
  free(waste[0]);
  free(waste[1]);
  return 0;
}