Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1242-3fcb876e
この記事にトラックバックする(FC2ブログユーザー)

Open 2010 Qual. 2 MEDIUM - FuzzyLife (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Qualification Round 2 MEDIUM (500pt)
Problem Statement
TopCoderニコ生オープン 第1回 自分の参加記録

問題概要

ライフゲーム.近傍は上下左右斜め8マスを意味する.
各マスは,
 今生きてると,近傍に生きてるマスが2つまたは3つだけあると生き残れる
 今死んでると,近傍に生きてるマスが3つだけあると生き返る
無限に広いグリッドの一部分として,50*50以下ののグリッドが与えられる.
そのグリッドの外は全部死んでる.
で,グリッド中に幾つか?が与えられるので,それが死んでるか生きてるか自由に決めて良くて,1ターン後に生きてるマスの数の最大値を求める問題.
ただし,全てのセルにおいて,隣接してる?の数は高々1つまで.

解法

各?について,独立に考えれば良い.
死んでる状態にするか,生きてる状態にするか,自分とその近傍が1ターン後に生きてる個数が多い方を採用する.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int x,y;
vector<string> in;

int get_state(int a,int b){
  if(a<0||b<0||a>=x||b>=y) return 0;
  return in[a][b]-'0';
}

int cnt(int a,int b){
  int i,j,res=0;
  REP(i,-1,2) REP(j,-1,2) if(i||j) res+=get_state(i+a,j+b);
  return res;
}

int is_live(int a,int b){
  int i=get_state(a,b);
  int j=cnt(a,b);
  if(i==1 && (j==2||j==3)) return 1;
  if(i==0 && j==3) return 1;
  return 0;
}

class FuzzyLife {
public:
int survivingCells(vector <string> in_) {
  int i,j,a,b,di,dj;
  int res=0;

  in=in_;
  x=in.size(); y=in[0].size();

  rep(i,x) rep(j,y) if(in[i][j]=='?'){
    a=b=0;
    
    in[i][j]='0';
    REP(di,-1,2) REP(dj,-1,2) if(di||dj) a += is_live(i+di,j+dj);
    
    in[i][j]='1';
    REP(di,-1,2) REP(dj,-1,2) if(di||dj) b += is_live(i+di,j+dj);

    if(a>b) in[i][j]='0';
  }

  REP(i,-1,x+1) REP(j,-1,y+1) res += is_live(i,j);

  return res;
}

};

以下はTopCoderニコ生Open本番中にサブミットしたコード.

// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int x,y;
vector<string> in;

int get_state(int a,int b){
  if(a<0||b<0||a>=x||b>=y) return 0;
  return in[a][b]-'0';
}

int cnt(int a,int b){
  int i,j,k=0;
  int ii, jj;

  REP(i,-1,2) REP(j,-1,2) if(i||j){
    ii=i+a; jj=j+b;
    if(ii<0||jj<0||ii>=x||jj>=y) continue;
    if(in[ii][jj]=='1') k++;
  }

  return k;
}

class FuzzyLife {
public:
int survivingCells(vector <string> in_) {
  int i,j,k,m;
  int a,b,ii,jj,di,dj;
  int res=0;

  in=in_;
  x=in.size(); y=in[0].size();

  rep(i,x) rep(j,y) if(in[i][j]=='?'){
    in[i][j]='0'; m=0;
    REP(di,-1,2) REP(dj,-1,2) if(di||dj){
      ii=i+di; jj=j+dj;
      k=cnt(ii,jj);
      if(get_state(ii,jj) && (k==2||k==3)) m++;
      if(!get_state(ii,jj) && k==3) m++;
    }
    a=m;
    
    in[i][j]='1'; m=0;
    REP(di,-1,2) REP(dj,-1,2) if(di||dj){
      ii=i+di; jj=j+dj;
      k=cnt(ii,jj);
      if(get_state(ii,jj) && (k==2||k==3)) m++;
      if(!get_state(ii,jj) && k==3) m++;
    }
    b=m;

    if(a>b) in[i][j]='0';
  }

  REP(i,-1,x+1) REP(j,-1,y+1){
    k=get_state(i,j);
    m = cnt(i,j);
    if(k && (m==2||m==3)) res++;
    if(!k && m==3) res++;
  }

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1242-3fcb876e
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。