Midpoint Erase [yukicoder No.601] - はまやんはまやんはまやん

解法

消せる点のペアの間に辺を引いてみると、連結成分は完全グラフになっていることが分かる。
解説にもあったが、点をxとyの偶奇で4グループに分ける。
すると、各グループは完全グラフとなっており、グループとグループの間に辺は無い。
ゲームの行動はグラフから1つ辺を選んで端点を取り除く作業と言える。
完全グラフであれば、n点からfloor(n/2)回だけ行動を行える。
よって、どんな行動をしても「floor(グループの頂点/2)の総和」だけ行動できる。
最高行動回数が奇数ならば、Aliceが行動して終わるので、Aliceの勝ち。
偶数ならば、Bobが行動して終わるので、Bobの勝ち。

int N, cnt[4];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int x, y; cin >> x >> y;
        x %= 2;
        y %= 2;
        cnt[y * 2 + x]++;
    }

    int sm = 0;
    rep(i, 0, 4) sm += cnt[i] / 2;
    if (sm % 2 == 1) printf("Alice\n");
    else printf("Bob\n");
}