Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2011-11-13

SRM523 900

| 08:13 | はてなブックマーク - SRM523 900 - cafelier@SRM

思ったより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解読んでみた。ビットマスクで補集合になる相手を探すのは単にソートして上からと下から順に見ていくだけでよいのかー。なるほど。

トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20111113
 | 

presented by cafelier/k.inaba under CC0