Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 10001 - Garden of Eden (この記事を編集する[管理者用])

Source
UVa 10001

問題概要
n文字のビット列aから新しいn文字のビット列bを次のように決める.
 b[k] = f(a[k-1 mod n],a[k],a[k+1 mod n])
fとbが与えられたときに,対応するaが存在するかどうかを判定する問題.
nは32以下.

解法
DP.
状態は,固定した場所のaの2文字 * 現在見ている場所のaの2文字 * 現在見ている場所,で状態数は4*4*32程度.

C言語のスパゲッティなコード
#include<stdio.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int cnv,n;
char in[1000];
int dp[4][4][33];

int get(int k){ if(cnv&(1<<k)) return 1; return 0; }

int sol(int last,int nex,int now){
  int i,j,k,res=0;
  if(dp[last][nex][now]>=0) return dp[last][nex][now];

  if(now==n-1){
    k = (nex/2)*4 + last;
    if(get(k)!=in[n-1] || last/2!=nex%2) return dp[last][nex][now]=0;
    return dp[last][nex][now]=1;
  }

  rep(i,2){
    k=nex*2+i;
    if(in[now]!=get(k)) continue;
    res |= sol(last,k%4,now+1);
  }

  return dp[last][nex][now]=res;
}

int main(){
  int i,j,k,l,m;

  while(scanf("%d%d%s",&cnv,&n,in)==3){
    rep(i,4) rep(j,4) rep(k,n) dp[i][j][k]=-1;
    rep(i,n) in[i]-='0';
    k=0; rep(i,4) k |= sol(i,i,0);
    if(k) puts("REACHABLE"); else puts("GARDEN OF EDEN");
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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