TopCoder SRM 549 Div2 Hard: OrderOfTheHats

解法

NをYにするのは意味が無いので、YをNにすることだけ考える。

各spellを覚えたかどうかをビットマスクで管理し、新しくスペルを覚えるのに潰さなければならないYの個数をコストとしてダイクストラする。

コード

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> P;
class OrderOfTheHats {
  int bitCount(long x) {
    x = (x & 0x55555555) + (x >> 1 & 0x55555555);
    x = (x & 0x33333333) + (x >> 2 & 0x33333333);
    x = (x & 0x0f0f0f0f) + (x >> 4 & 0x0f0f0f0f);
    x = (x & 0x00ff00ff) + (x >> 8 & 0x00ff00ff);
    return (x & 0x0000ffff) + (x >> 16 & 0x0000ffff);
  }

 public:
  int minChanged(vector<string> spellChart) {
    int N = spellChart.size();
    vector<int> masks(N);
    for (int j = 0; j < N; ++j) {
      int mask = 0;
      for (int i = N - 1; i >= 0; --i) {
        mask *= 2;
        if (spellChart[i][j] == 'Y') mask += 1;
      }
      masks[j] = mask;
    }

    vector<int> dist((1 << N), 1e8);
    vector<bool> vis((1 << N), false);
    dist[0] = 0;
    priority_queue<P, vector<P>, greater<P>> Q;
    Q.emplace(0, 0);
    while (!Q.empty()) {
      int bit = Q.top().second;
      Q.pop();
      if (vis[bit]) continue;
      vis[bit] = true;
      for (int i = 0; i < N; ++i) {
        int delta = masks[i] - (masks[i] & bit);
        int cost = bitCount(delta);
        int next = bit | (1 << i);
        if (dist[next] <= dist[bit] + cost) continue;
        dist[next] = dist[bit] + cost;
        if (next == (1 << N) - 1) return dist[next];
        Q.emplace(dist[next], next);
      }
    }
    return dist[(1 << N) - 1];
  }
};