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