cafelier@SRM

SRM487 550

あとで | 18:57 |

• 考え方はあってたんだけど酷いミスがありました

class BunnyExam { public:
   double getExpected(int m, int k, vector <int> linkage) 
   {
      // trivially impossible cases
      if( k==1 && m>1   )
         return -1;
      if( k==2 )
         for(int i=0; i<linkage.size(); i+=2)
            if( (linkage[i] ^ linkage[i+1])&1 )
               return -1;
      for(int i=0; i<linkage.size(); i+=2)
         if( abs(linkage[i] - linkage[i+1]) == 1 )
            return -1;

      // interference graph
      int M = linkage.size()/2;
      vector< vector<int> > conflict(M);
      for(int i=0; i<M; ++i)
      for(int j=0; j<M; ++j)
         if( abs(linkage[2*i+0]-linkage[2*j+0])==1 || abs(linkage[2*i+1]-linkage[2*j+0])==1
          || abs(linkage[2*i+0]-linkage[2*j+1])==1 || abs(linkage[2*i+1]-linkage[2*j+1])==1 )
            conflict[i].push_back(j);

      // check k-colorability
      if( colorable(conflict, k) )
         return double(m)/k;
      else
         return -1;
   }

   bool colorable(vector< vector<int> >& G, int k)
   {
      if( G.size() <= k )
         return true;
      vector<int> color(G.size(), (1<<k)-1);
      color[0] = 1;
      return rec(G, color, 0);
   }

   bool rec(vector< vector<int> >& G, /*const*/ vector<int>& cl, int i)
   {
      if( i == cl.size() )
         return true;
      for(int k=1; k<=cl[i]; k<<=1)
         if( cl[i] & k ) // use color k
         {
            vector<int> clcl = cl;
            for(int j=0; j<G[i].size(); ++j) // G[i][j] cannot use k
               clcl[G[i][j]] &= ~k;
            if( rec(G, clcl, i+1) )
               return true;
            // 本番では、なぜかここに cl.swap(clcl); という余計な一行があった…orz
         }
      return false;
   }
};

• cl じゃなくて、ちゃんとした名前をつけるべきなんだよなあ。反省。