Hatena::Grouptopcoder

cafelier@SRM

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

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

 | 

2010-07-01

SRM474 1000

| 13:29 | はてなブックマーク -  SRM474 1000 - cafelier@SRM

  • 大筋ではあってた。submitしたものから
    • メモ化の表をmapからvectorにして7倍速
    • subtreeのノード数と割り当てようとしているグラフのノード数が一致していることのチェックを、グラフノードからルートを割り当てるループより先に回したら4倍速
    • くらいで。まあ後者はそりゃそう書かなきゃだなあ。

template<typename T>
struct DP3
{
   int N1, N2, N3;
   vector<T> data;
   DP3(){}
   DP3(int N1, int N2, int N3, const T& t = T())
      : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); }
   T& operator()(int i1, int i2, int i3)
      { return data[ ((i1*N2)+i2)*N3+i3 ]; }
   void swap(DP3& rhs)
      { data.swap(rhs.data); }
};

class GameWithGraphAndTree { public:
   vector<string>        graph;
   vector< vector<int> > children;
   vector<int>           subtree_size;

   int calc(vector <string> graph_, vector <string> tree_) 
   {
      int N = graph_.size();

      graph = graph_;
      children.resize(N);
      subtree_size.resize(N);
      computeChildren(-1, 0, tree_);

      memo = DP3<LL>(N,N,1<<N,-1);

      LL answer = 0;
      for(int gv=0; gv<graph.size(); ++gv)
         answer += vertical(0, gv, (1<<N)-1);
      return int(answer % 1000000007);
   }

   void computeChildren(int tparent, int tv, const vector<string>& tree)
   {
      subtree_size[tv] = 1;
      for(int tc=0; tc<tree.size(); ++tc)
         if( tree[tv][tc] == 'Y' && tc!=tparent ) {
            children[tv].push_back(tc);
            computeChildren(tv, tc, tree);
            subtree_size[tv] += subtree_size[tc];
         }
   }

   LL vertical(int tv, int gv, int mask)
   {
      return horizontal(tv, gv, mask&~(1<<gv), 0); 
   }

   DP3<LL> memo;
   LL horizontal(int tv, int gv, int mask, int i)
   {
      if( i == children[tv].size() ) 
         return 1;
      int tu = children[tv][i];

      if( memo(tv,gv,mask) >= 0 )
         return memo(tv,gv,mask);

      LL answer = 0;
      for(int subset=mask; subset; subset=(subset-1)&mask)
         if( __builtin_popcount(subset) == subtree_size[tu] )
            for(int gu=0; (1<<gu)<=subset; ++gu)
               if( graph[gv][gu]=='Y' && ((1<<gu)&subset) )
                  answer += vertical(tu, gu, subset) * horizontal(tv, gv, mask&~subset, i+1);

      return memo(tv,gv,mask) = answer % 1000000007;
   }
};
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20100701
 | 

presented by cafelier/k.inaba under CC0