cafelier@SRM

SRM525 525

あとで | 00:10 |

なるほどなあ。

class Rumor { public:
   int getMinimum(string knowledge, vector <string> graph)
   {
      const int N = knowledge.size();
      const int ALL = (1<<N) - 1;

      // Turn the input into bit-vectors.
      int know=0;
      for(int v=0; v<N; ++v)
         know |= (knowledge[v]=='Y') << v;
      vector<int> g(N);
      for(int v=0; v<N; ++v)
      for(int u=0; u<N; ++u)
         g[v] |= (graph[v][u]=='Y') << u;

      // Try all possible patterns (which rumor each rabit spreads first when she knows both), and simulate.
      int best = N+1;
      for(int preferA=0; preferA<(1<<N); ++preferA)
         for(int knowA=know, knowB=know, didA=0, didB=0, step=0; step<best; ++step) {
            if( knowA==ALL && knowB==ALL )
               {best=step; break;}

            int doA=0, doB=0;
            for(int v=0; v<N; ++v) {
               bool a_ok = (knowA & 1<<v) && !(didA & 1<<v);
               bool b_ok = (knowB & 1<<v) && !(didB & 1<<v);
               doA |= (a_ok && b_ok && (preferA & 1<<v) || a_ok && !b_ok) << v;
               doB |= (a_ok && b_ok && !(preferA & 1<<v) || !a_ok && b_ok) << v;
            }
            didA |= doA;
            didB |= doB;
            for(int v=0; v<N; ++v) {
               if(doA & 1<<v) knowA |= g[v];
               if(doB & 1<<v) knowB |= g[v];
            }
         }
      return best==N+1 ? -1 : best;
   }
};