cafelier@SRM

SRM527 275

あとで | 05:24 |

みんなDPだった。Easyだからもっと格好いい解があるのかとずっと考えてしまいました…。

• 「Nノード ＆ N-1エッジ ＆ 連結 ＝ 木」という知識だけ使う

class P8XGraphBuilder { public:
   int solve(vector <int> scores)
   {
      scores.insert(scores.begin(), 9999999); // 1ずれてると扱いにくいので
      const int N = scores.size();

      // 葉の個数を全パターン試して良いのを取る
      int best = 0;
      for(int leaves=1; leaves<N; ++leaves)
         best = max(best, scores[1]*leaves + calc(leaves, N-leaves, scores));
      return best;
   }

   // 葉がleaves個、葉以外がnodes個の木のベストスコア
   map<pair<int,int>,int> memo;
   int calc(int leaves, int nodes, const vector<int>& scores)
   {
      // nodes==1 なら根を作らないといけないので全部
      if( nodes == 1 )
         return scores[leaves];

      // メモ化
      pair<int,int> key(leaves, nodes);
      if( memo.count(key) )
         return memo[key];

      // 適当にk個選んで1つのノードを親にする
      // この親ノードは根では無いので次数は k+1。
      int best = 0;
      for(int k=1; k<=leaves; ++k)
         best = max(best, scores[k+1] + calc(leaves-k+1, nodes-1, scores));
      return memo[key] = best;
   }
};

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;
   }
};