cafelier@SRM

SRM476 550

あとで | 18:12 |

• 方針はあってた

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

class FriendTour { public:
   double tourProbability(vector <string> friends, int K) 
   {
      int N = (int)friends.size();
      vector< vector<int> > f(N);
      for(int i=0; i<N; ++i)
      {
         stringstream sin( friends[i] );
         for(int v; sin>>v; )
            f[i].push_back(v-1);
      }

      map<int,int> rename;
      rename[0] = 0;
      for(int k=0; k<f[0].size(); ++k)
      {
         int newid = rename.size();
         rename[f[0][k]] = newid;
      }

      vector< vector<int> > ff(rename.size());
      for(int i=0; i<N; ++i)
         if( rename.count(i) )
         {
            int k = rename[i];
            for(int j=0; j<f[i].size(); ++j)
               if( f[i][j]!=0 && rename.count(f[i][j]) )
                  ff[k].push_back( rename[f[i][j]] );
               else
                  ff[k].push_back( -1 );
         }
      return solve(ff, K);
   }

   double solve(vector<vector<int> >& f, int K)
   {
      memo = DP2<double>(f.size(), 1<<f.size(), -1);
      return rec(f, K, 0, 1);
   }

   double C(int N, int K)
   {
      double p = 1.0;
      for(int i=0; i<min(K,N-K); ++i)
         p = p * (N-i) / (1+i);
      return p;
   }

   DP2<double> memo;
   double rec(vector<vector<int> >& f, int K, int v, int mask)
   {
      if( memo(v,mask) != -1 )
         return memo(v,mask);

      if( mask == (1<<f.size())-1 )
         return 1.0;

      vector<double> nxt;
      for(int i=0; i<f[v].size(); ++i)
         if( f[v][i]==-1 || (mask & (1<<f[v][i])) )
            nxt.push_back(0);
         else
            nxt.push_back( rec(f,K,f[v][i],mask|(1<<f[v][i])) );
      sort(nxt.rbegin(), nxt.rend());
      int N = nxt.size();
      if( N == 0 )
         return memo(v,mask) = 0.0;

      if( N <= K )
         return memo(v,mask) = nxt[0];

      double p = 0.0;
      for(int i=0; i<nxt.size(); ++i) {
         if( N-1-i < K ) {
            p += C(N-i,K) / C(N,K) * nxt[i];
            break;
         }
         p += (C(N-i,K) - C(N-1-i,K)) / C(N,K) * nxt[i];
      }
      return memo(v,mask) = p;
   }
};

• 状態数 N・2^N、１状態ごとの計算に N 回 C(N,K) を呼んでいるので
• O(K・N^2・2^N) かな。たぶんC(N,K)の計算をもっとまともに高速化しないと本当は時間が危ないけど通ったからいいや