SRM 525 div1 med:Rumor
解法
「それぞれの人が A と B どちらの噂を先に伝えるか」で 2^n 通りの場合分けをして, それぞれの場合についてシミュレーションします。
const int INF = 1e9; const int MAXN = 20; bool done[MAXN]; class Rumor { public: int getMinimum(string knowledge, vector <string> graph) { int n = knowledge.size(); int ret = INF; vector<int> can(n, 0); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (graph[i][j] == 'Y') can[i] |= 1 << j; } } for (int s = 0; s < (1<<n); s++) { memset(done, false, sizeof(done)); int A = 0, B = 0; for (int i = 0; i < n; i++) if (knowledge[i] == 'Y') { A |= 1<<i; B |= 1<<i; } int cnt = 0; while (cnt < 20) { if (A == (1<<n)-1 && B == (1<<n)-1) break; int nA = A, nB = B; cnt++; for (int i = 0; i < n; i++) { if (!done[i]) { // A if ((s>>i)&1) { if ((A>>i)&1) { nA |= can[i]; done[i] = true; } } else { if ((B>>i)&1) { nB |= can[i]; done[i] = true; } } } else { if ((s>>i)&1) { if ((B>>i)&1) { nB |= can[i]; } } else { if ((A>>i)&1) { nA |= can[i]; } } } } A = nA, B = nB; } ret = min(ret, cnt); } if (ret >= 20) return -1; return ret; } };