cafelier@SRM

SRM464 1000

あとで | 10:16 |

提出したバージョンはTLEなだけでなく間違ってたけど、多少の修正で直せたみたい。タイムはとりあえず「THE・GORIOSHI」で通した。

class ColorfulMaze { public:
   double getProbability(vector <string> maze, vector <int> trap) 
   {
      return solve(maze, trap, 0);
   }

   typedef int vert;

   double solve(const vector<string>& maze, const vector<int>& trap, int damage)
   {
      const int H = maze.size();
      const int W = maze[0].size();

      // R[i] == list of cells colored 'A'+i and reachable from '$'
      vector<vert> R[7];
      {
         stack<vert>  Q;
         vector<bool> V(H*W);
         for(int y=0; y<H; ++y)
            for(int x=0; x<W; ++x)
               if( maze[y][x] == '$' )
                  {Q.push(y*W+x); V[y*W+x]=1;}

         while( !Q.empty() ) {
            vert v=Q.top(); Q.pop();
            int y=v/W, x=v%W;

            int dy[]={-1,+1,0,0}, dx[]={0,0,-1,+1};
            for(int i=0; i<4; ++i) {
               int yy=y+dy[i], xx=x+dx[i],u=yy*W+xx;
               if( 0<=yy && yy<H && 0<=xx && xx<W && maze[yy][xx]!='#' && !V[u] ) {
                  if( maze[yy][xx]=='!' )
                     return 1.0;
                  V[u]=1;
                  if( maze[yy][xx] == '.' )
                     Q.push(u);
                  else
                     R[maze[yy][xx]-'A'].push_back(u);
               }
            }
         }
      }

      double pMax = 0.0;
      for(int k=0; k<7; ++k) if(!R[k].empty()) {
         double p = 0; // prob. to survive when you first step in the color 'A'+k

         vector<string> m = maze;
         { // the case it was not a trap
            for(int y=0; y<H; ++y)
               for(int x=0; x<W; ++x)
                  if(maze[y][x]=='A'+k)    m[y][x] = '.';
                  else if(maze[y][x]=='$') m[y][x] = ".#"[damage];
            for(int i=0; i<R[k].size(); ++i)
               m[R[k][i]/W][R[k][i]%W] = '$';
            p = (1-trap[k]/100.0) * solve(m, trap, damage); 
         }
         if( damage == 0 ) { // the case it was a trap
            for(int y=0; y<H; ++y)
               for(int x=0; x<W; ++x)
                  if(maze[y][x]=='A'+k && m[y][x]!='$') m[y][x] = '#';
            p += (trap[k]/100.0) * solve(m, trap, damage+1);
         }

         pMax = max(pMax, p); // take the maximum
      }
      return pMax;
   }
};

• サーバで1.9secくらい。トラップ床を踏む順番7!通りを全部試す感じで。
• 想定解はなんかこれメモ化するのかなあと思ったのだけど、7! も 3^7 (踏んでない/踏んで罠だった/罠じゃなかった、の3通りずつ)もそこまで大差ないよなー。ううむ