ACM-ICPC 2011 日本国内予選(演習)

参加資格はないのですが、ACM-ICPC2011日本国内予選の問題を時間を測って解いてみました。解けたのは3問です。

Aは似たような問題を昔自作して解いたことがあるので、あまり苦労しませんでした。その当時(数年前)は1個1個判定していましたが、今回はエラトステネスの篩で素数表を作りました。

BはUTPC2011(東京大学プログラミングコンテスト)で少々似たような問題を見たことがあるなと思いながら、スタックを作って解きました。Cでスタックを組むのが面倒だったので、スタック風の処理、という方が正確かも知れませんが。

Cはバックトラックで実装しました。日本国内予選ではセルを数える問題が結構多いような気がしますが、単なる偶然でしょうか？

問題はこちらです。

ソースはC言語です。

A.チェビシェフの定理
#include<stdio.h>
#include<stdlib.h>

#define NUM 123456

unsigned int list[NUM];

void makelist(void);

int main(void){
  unsigned int i,j,n,ans;
  makelist();
  while(scanf("%u",&n) && n){
    ans=0;
    if(n==1){
      puts("1");
      continue;
    }else if(n==2){
      puts("1");
      continue;
    }
    for(i=((n+1)>>1);i<n;i++) if(list[i]!=0) ans++;
    printf("%u\n",ans);
  }
  return 0;  
}

void makelist(void){
  unsigned int i,j;
  for(i=0;i<NUM;i++) list[i]=(i<<1)+1;
  for(i=1;i*i<NUM;i++){
    if(list[i]==0) continue;
    for(j=(i*(i+1))<<1;j<NUM;j+=(i<<1)+1) list[j]=0;
  }
}

B.世界の天秤
#include<stdio.h>
#include<string.h>

#define NUM 100

int main(void){
  int brac[NUM+1],now,i,flg;
  char str[NUM+2];
  while(fgets(str,sizeof(str),stdin) && strcmp(str,".\n")){
    memset(brac,0,sizeof(brac));
    flg=0;
    now=0;
    for(i=0;i<strlen(str)-1;i++){
      if(str[i]=='('){
brac[now]=1;
now++;
      }else if(str[i]=='['){
brac[now]=2;
now++;
      }else if(str[i]==')'){
if(now==0 || brac[now-1]!=1){
 flg=1;
 break;
}
now--;
      }else if(str[i]==']'){
if(now==0 || brac[now-1]!=2){
 flg=1;
 break;
}
now--;
      }
    }
    if(now!=0) flg=1;
    if(flg==0) puts("yes");
    else puts("no");
  }
  return 0;
}

C.同色パネル結合
#include<stdio.h>
#include<stdlib.h>

typedef struct{
  int col;
  int check;
} panels;

int max,h,w,c,num;

void getmax(panels **panel,int color,int nest,int n);
void change(panels **panel,int color,int i,int j);
void countnum(panels **panel,int i,int j);


int main(void){
  panels **panel;
  int i,j,colors;
  while(scanf("%d %d %d",&h,&w,&c) && h && w && c){
    panel=(panels **)calloc(h,sizeof(panels *));
    for(i=0;i<h;i++) *(panel+i)=(panels *)calloc(w,sizeof(panels *));
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
scanf("%d",&colors);
(*(panel+i)+j)->col=colors;
(*(panel+i)+j)->check=0;
      }
    }
    max=0;
    for(i=0;i<6;i++) getmax(panel,i+1,0,0);
    printf("%d\n",max);
    for(i=0;i<h;i++) free(*(panel+i));
    free(panel);
  }
  return 0;
}

void getmax(panels **panel,int color,int nest,int n){
  panels **tmp;
  int i,j,k;
  if(nest==4 && color!=c) return;
  tmp=(panels **)calloc(h,sizeof(panels *));
  for(i=0;i<h;i++) *(tmp+i)=(panels *)calloc(w,sizeof(panels *));
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      (*(tmp+i)+j)->col=(*(panel+i)+j)->col;
      (*(tmp+i)+j)->check=0;
    }
  }
  change(tmp,color,0,0);
  num=0;
  countnum(tmp,0,0);
  if(max<num) max=num;
  if(nest==4 || num==n){
    for(i=0;i<h;i++) free(*(tmp+i));
    free(tmp);
    return;
  }
  for(i=0;i<6;i++) getmax(tmp,i+1,nest+1,1);
  for(i=0;i<h;i++) free(*(tmp+i));
  free(tmp);
}

void change(panels **panel,int color,int i,int j){
  (*(panel+i)+j)->check=1;
  if(i>0 && (*(panel+i)+j)->col==(*(panel+i-1)+j)->col && (*(panel+i-1)+j)->check==0) change(panel,color,i-1,j);
  if(i<h-1 && (*(panel+i)+j)->col==(*(panel+i+1)+j)->col && (*(panel+i+1)+j)->check==0) change(panel,color,i+1,j);
  if(j>0 && (*(panel+i)+j)->col==(*(panel+i)+j-1)->col && (*(panel+i)+j-1)->check==0) change(panel,color,i,j-1);
  if(j<w-1 && (*(panel+i)+j)->col==(*(panel+i)+j+1)->col && (*(panel+i)+j+1)->check==0) change(panel,color,i,j+1);
  (*(panel+i)+j)->col=color;
}

void countnum(panels **panel,int i,int j){
  (*(panel+i)+j)->check=2;
  if(i>0 && (*(panel+i)+j)->col==(*(panel+i-1)+j)->col && (*(panel+i-1)+j)->check!=2) countnum(panel,i-1,j);
  if(i<h-1 && (*(panel+i)+j)->col==(*(panel+i+1)+j)->col && (*(panel+i+1)+j)->check!=2) countnum(panel,i+1,j);
  if(j>0 && (*(panel+i)+j)->col==(*(panel+i)+j-1)->col && (*(panel+i)+j-1)->check!=2) countnum(panel,i,j-1);
  if(j<w-1 && (*(panel+i)+j)->col==(*(panel+i)+j+1)->col && (*(panel+i)+j+1)->check!=2) countnum(panel,i,j+1);
  num++;
}