cafelier@SRM

SRM523 900

あとで | 08:13 |

思ったよりTLE厳しかった。

#ifdef __GNUC__
   #include <ext/hash_map>
   #define unordered_map __gnu_cxx::hash_map
#else
   #include <unordered_map>
#endif

class AlphabetPaths { public:
   int H, W;
   long long count(vector <string> maze)
   {
      H = maze.size();
      W = maze[0].size();
      for(int y=0; y<H; ++y)
      for(int x=0; x<W; ++x)
         if( maze[y][x] != '.' )
            maze[y][x] = char(string("ABCDEFZHIKLMNOPQRSTVX").find(maze[y][x]));

      LL total = 0;
      for(int y=0; y<H; ++y)
      for(int x=0; x<W; ++x)
         if( maze[y][x] != '.' ) {
            int mid = maze[y][x];

            unordered_map<int, int> reachable;
            travel(1, 1<<mid, y, x, maze, reachable);

            for(unordered_map<int,int>::iterator it=reachable.begin(); it!=reachable.end(); ++it)
            {
               unordered_map<int,int>::iterator kt = reachable.find((((1<<21)-1)^it->first) | (1<<mid));
               if( kt != reachable.end() )
                  total += LL(it->second) * kt->second;
            }
         }
      return total;
   }

   void travel(int n, int mask, int y, int x, const vector<string>& maze,
               unordered_map<int,int>& reachable)
   {
      if( n == 11 ) {
         reachable[mask]++;
         return;
      }

      static const int dy[] = {-1,+1,0,0};
      static const int dx[] = {0,0,-1,+1};
      for(int i=0; i<4; ++i) {
         int yy = y+dy[i];
         int xx = x+dx[i];
         if( 0<=yy && yy<H && 0<=xx && xx<W && maze[yy][xx]!='.' ) {
            int v = maze[yy][xx];
            if( !(mask & (1<<v)) )
               travel(n+1, mask|(1<<v), yy, xx, maze, reachable);
         }
      }
   }
};

真ん中の点を全通り試して、10歩歩くパターンを全列挙して、始点側と終点側と見なしてかけ算の総和。std::mapだとわずかに最悪ケースで間に合わなかったので、あまり気が進まないけどハッシュマップにしてみた。想定解はなんだろう。

Petr解読んでみた。ビットマスクで補集合になる相手を探すのは単にソートして上からと下から順に見ていくだけでよいのかー。なるほど。