cafelier@SRM

SRM527 450

あとで | 05:02 |

「辞書順最小解を求めよ」の黄金パターン

1. 解があるかないかの判定だけするルーチンを作る
2. 先頭から「１文字決めてみる→解があるか判定／なければ次の文字」のループで順に確定

//=== 二部グラフマッチングライブラリ ===
typedef int           vert;
typedef vert          edge;
typedef vector<edge>  edges;
typedef vector<edges> graph;

bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] )
{
   for(int i=0; i<G[v].size(); ++i) {
      vert u = G[v][i];
      if( visited[u] ) continue;
      visited[u] = true;

      if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) )
         { matchTo[v]=u, matchTo[u]=v; return true; }
   }
   return false;
}

template<int NV>
int biMatch( graph& G, int L ) // [0,L):left, [L,?):right
    // only left->right edges are used during computation
{
   vector<vert> matchTo(G.size(), -1);
   int ans = 0;
   for(vert v=0; v<L; ++v) {
      bool visited[NV] = {};
      if( augment(G, v, matchTo, visited) )
         ++ans;
   }
   return ans;
}
//=== ここまで ===

class P8XMatrixRecovery { public:
   int H, W;
   vector <string> solve(vector <string> rows, vector <string> columns)
   {
      H = rows.size();
      W = rows[0].size();
      for(int y=0; y<H; ++y)
      for(int x=0; x<W; ++x) // 左から順に決めていく
         if( rows[y][x] == '?' ) {
            rows[y][x] = '0'; // 0と決めうち
            if( !can(rows, columns) ) // 0にしちゃうとマッチングが無くなるようなら
               rows[y][x] = '1'; // 1にすべき
         }
      return rows;
   }

   bool can(const vector<string>& rows, const vector<string>& columns)
   {
      graph G(W*2);
      for(int x1=0; x1<W; ++x1) {
         string left;
         for(int y=0; y<H; ++y)
            left += rows[y][x1];
         for(int x2=0; x2<W; ++x2)
            if( match(left, columns[x2]) ) 
               G[x1].push_back(x2+W);
      }
      return biMatch<60>(G, W) == W;
   }

   bool match( const string& l, const string& r )
   {
      for(int i=0; i<l.size(); ++i)
         if( l[i]!=r[i] && l[i]!='?' && r[i]!='?' )
            return false;
      return true;
   }
};