SRM 561 CirclesGame

問題

TopCoder Statistics - Problem Statement

Alice と Bob がゲームをする。ゲームは交差しないいくつかの円が書かれた平面上で行う。

• まだ円内に赤点がない円を選ぶ。
• その円内に赤点をいれる。
• 赤点を入れることができないほうが負け。

両者が最適に動いた場合, 勝つのはどちらか。

解法

見るからに円の内外関係は木の構造をしています。この内外関係がいくつかの木を形成するので, 全体としては森です。

「ある円を選ぶ」という操作は, 「木のある頂点を選ぶ」という操作に対応していて, 「ある円を選んだ時にもう選ぶことができなくなる円」は「対応する頂点の先祖」に対応します。

ゲームは nim で表すことができるので, 各木ごとにその grundy 数を求め, xor を取れば良いです。

vi x, y, r;
vector<int> parent;

int square(int x) {
    return x*x;
}

// i が j の中にあるか
bool isInside(int i, int j) {
    return r[i] <= r[j] && square(x[i]-x[j])+square(y[i]-y[j]) <= square(r[j]);
}

int g[55];
int grundy(int i) {
    int& ret = g[i];
    if (ret >= 0) return ret;
    int n = x.size();
    set<int> S;
    for (int j = 0; j < n; j++) {
        if (isInside(j, i)) {
            vi remove;
            for (int k = 0; k < n; k++) {
                if (isInside(k, i) && isInside(j, k)) remove.push_back(k);
            }
            int r = 0;
            for (int k = 0; k < n; k++) if (isInside(k, i)) {
                bool ok = false;
                for (int v : remove) {
                    if (parent[k] == v) {
                        ok = true;
                    }
                    if (k == v) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    r ^= grundy(k);
                }
            }
            S.insert(r);
        }
    }
    ret = 0;
    while (1) {
        if (S.find(ret) == S.end()) return ret;
        ret++;
    }
}

class CirclesGame {
public:
    string whoCanWin(vector <int> _x, vector <int> _y, vector <int> _r) {
        x = _x, y = _y, r = _r;
        int n = x.size();
        parent.clear();
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            int minR = 1000000, p = -1;
            for (int j = 0; j < n; j++) {
                if (i != j && isInside(i, j)) {
                    if (minR > r[j]) {
                        minR = r[j];
                        p = j;
                    }
                }
            }
            parent[i] = p;
        }
        int x = 0;
        memset(g, -1, sizeof(g));
        for (int i = 0; i < n; i++) if (parent[i] == -1) {
            x ^= grundy(i);
        }
        if (x) return "Alice";
        else return "Bob";
    }
};