Hatena::Grouptopcoder

cafelier@SRM

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

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

 | 

2011-11-30

SRM525 525

| 00:10 | はてなブックマーク -  SRM525 525 - cafelier@SRM

なるほどなあ。

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;
   }
};
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20111130
 | 

presented by cafelier/k.inaba under CC0