cafelier@SRM

SRM425 Div1 1000

あとで | 15:28 |

• あまりに解けないものは Editorial を見るのを解禁することにした

class RoadsOfKingdom { public:
   vector< vector<double> > P;

   double getProbability(vector <string> roads) 
   {
      P     = read_input(roads);
      memo  = vector<double>(1<<P.size(), -1);
      memo0 = vector<double>(P.size()<<P.size(), -1);
      memo1 = vector<double>(P.size()<<P.size(), -1);
      return prob_tree( (1<<P.size())-1 );
   }

   vector< vector<double> > read_input(const vector<string>& R)
   {
      int N = R.size();
      vector< vector<double> > P(N, vector<double>(N));
      for(int i=0; i<N; ++i)
         for(int j=0; j<N; ++j)
            P[i][j] = (R[i][j] - '0') / 8.0;
      return P;
   }

   vector<double> memo;
   double prob_tree(int S)
   {
      if( memo[S] >= 0 )
         return memo[S];

      // the first and the second smallest IDs in S
      int v, w;
      for(v=0;   (1<<v)<=S; ++v) if( S & 1<<v ) break;
      for(w=v+1; (1<<w)<=S; ++w) if( S & 1<<w ) break;

      // if |S| < 2 then it always forms a tree
      if( (1<<w) > S )
         return memo[S] = 1.0;

      // Let's consider v as the "root node" of S, and try all possible "subtrees" T containing w.
      // The situation is (other nodes)=v-(T where w in T)
      double p = 0.0;
      for(int T=S; T; T=(T-1)&S)
         if( (T & 1<<w) && !(T & 1<<v) )
            p += prob_tree(T) * prob_tree(S&~T) * prob_separated(T, S&~T&~(1<<v)) * prob_one(v, T);
      return memo[S] = p;
   }

   double prob_separated(int S1, int S2)
   {
      double p = 1.0;
      for(int v=0; (1<<v)<=S1; ++v) if( S1 & 1<<v )
         p *= prob_zero(v, S2);
      return p;
   }

   vector<double> memo0;
   double prob_zero(int v, int S) // 0 connection between v and S
   {
      const int key = v<<P.size() | S;
      if( memo0[key] >= 0 ) return memo0[key];

      double p = 1.0;
      for(int u=0; (1<<u)<=S; ++u) if( S & 1<<u )
         p *= 1.0 - P[v][u];
      return memo0[key] = p;
   }

   vector<double> memo1;
   double prob_one(int v, int S) // exactly 1 connection between v and S
   {
      const int key = v<<P.size() | S;
      if( memo1[key] >= 0 ) return memo1[key];

      double p = 0.0;
      for(int c=0; (1<<c)<=S; ++c) if( S & 1<<c )
      {
         double q = 1.0;
         for(int u=0; (1<<u)<=S; ++u) if( S & 1<<u )
            q *= u==c ? P[v][u] : 1-P[v][u];
         p += q;
      }
      return memo1[key] = p;
   }
};

• Leafから行くのではなくRootからトップダウンに行く
• 「Rootと、そこから繋がっている子供のうち最小のもの（を含むsubtree）」みたいにして集合を分割して再帰を降りると、どうしても O(N 3^N) になってしまうので
• かわりに
• 「Rootと、最小のもの（を含むsubtree）」と、Rootからの接続を考えない方がよい

• その辺はともかくとして、とりあえず、
• 「子供の数が不定の unranked tree でも、ビットDPするときはうまいこと"最初の子供の分だけとる"みたいにして2分割でビットDPが進むようにすると3^Nオーダーで行く、という感じのテクニックはunranked treeを扱うときに必須かも