Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM464 DIV1 HARD - ColorfulMaze (この記事を編集する[管理者用])

Source

TopCoder SRM464 DIV1 HARD (1000pt)
Problem Statement
SRM 464 自分の参加記録

問題概要

50*50以下の迷路に7種類のトラップが仕掛けられている.
それぞれのトラップが自分に取って有害の可能性が与えられる.
ある種類のトラップがもし自分に取って有害なら,他の同じ種類のトラップも有害で,無害だったら他も無害.
2回有害なトラップを通ると死ぬ.
スタートからゴールまで行くのに生存確率の最大値を求める問題.

解法

状態は
 有害だと判明しているトラップ×無害だと判明したトラップの集合×今の場所

 (7+1)*2^7*2500 = 2,560,000
ぐらいの状態数.
自由に行ったり来たり出来る状態は同じとみなしてDAGにしたのちDPする.
自分の実装が悪いだけかもしれないけど,意外と面倒な気がする.

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

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

void unionInit(int d[],int s){int i;rep(i,s)d[i]=i;}
int unionGet(int d[],int n){int t=n,k;while(d[t]!=t)t=d[t];while(d[n]!=n)k=d[n],d[n]=t,n=k;return n;}
int unionConnect(int d[],int a,int b){a=unionGet(d,a);b=unionGet(d,b);if(a==b)return 0;d[a]=b;return 1;}

#define N 3000000

int x, y, xy;
vector<string> mp; vector<int> trap;
int st, ed;

double prob[N];
int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};

int ind[N];

int encode(int sx,int sy,int smask,int stp){ return (stp*128+smask)*xy+sx*y+sy; }
void decode(int k,int *sx,int *sy,int *smask,int *stp){*sx=(k%xy)/y; *sy=k%y; k/=xy; *smask=k%128; *stp=k/128;}

double solve(int in){
  int k,t,X=unionGet(ind,in);
  int sx,sy,smask,stp,s, nx,ny,nmask,n;
  vector<int> stck;
  double res=0, tmp;

  // 毒を踏んだ直後の処理,ここから
  decode(in,&sx,&sy,&smask,&stp);
  if(mp[sx][sy]!='.' && mp[sx][sy]=='A'+stp){
    rep(k,4){
      nx=sx+dx[k]; ny=sy+dy[k];
      if(nx<0||ny<0||nx>=x||ny>=y||mp[nx][ny]=='#'||mp[nx][ny]=='A'+stp) continue;

      t=mp[nx][ny]-'A';
      if(mp[nx][ny]=='.' || smask&(1<<t)) tmp = solve(encode(nx,ny,smask,stp));
      else                                tmp = solve(encode(nx,ny,smask|(1<<t),stp)) * (100-trap[t]) / 100.0;

      if(res<tmp) res=tmp;
    }
    return res;
  }
  // 毒を踏んだ直後の処理,ここまで

  if(prob[X]>=-1) return prob[X]; // すでに求めていたら即座に返す

  stck.push_back(in);
  while(stck.size()){
    s=stck[stck.size()-1]; stck.pop_back();
    decode(s,&sx,&sy,&smask,&stp);

    if(sx*y+sy==ed) res=1;
    
    rep(k,4){
      nx=sx+dx[k]; ny=sy+dy[k];
      if(nx<0||ny<0||nx>=x||ny>=y||mp[nx][ny]=='#'||mp[nx][ny]=='A'+stp) continue;

      t=mp[nx][ny]-'A';
      if(mp[nx][ny]=='.' || smask&(1<<t)){
        n=encode(nx,ny,smask,stp);
        if(unionConnect(ind,s,n)) stck.push_back(n);
      } else {
        nmask = smask|(1<<t);
                   tmp  = solve(encode(nx,ny,nmask,stp)) * (100-trap[t]) / 100.0;
        if(stp==7) tmp += solve(encode(nx,ny,nmask,t  )) * trap[t]       / 100.0;
        if(res<tmp) res=tmp;
      }
    }
  }

//  decode(in,&sx,&sy,&smask,&stp); printf("%d %d : %d %d : %lf\n",sx,sy,smask,stp,res);
  return prob[unionGet(ind,in)]=res;
}

class ColorfulMaze {
public:
double getProbability(vector <string> mp_, vector <int> trap_) {
  int i,j;

  mp=mp_; trap=trap_; x=mp.size(); y=mp[0].size(); xy=x*y;
  rep(i,N) prob[i]=-2;
  unionInit(ind,N);

  rep(i,x) rep(j,y){
    if(mp[i][j]=='$') st=i*y+j, mp[i][j]='.';
    if(mp[i][j]=='!') ed=i*y+j, mp[i][j]='.';
  }

  return solve(7*128*xy+st);
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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