mayoko’s diary

プロコンとかいろいろ。

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