Codeforces Round #309 (Div.1) D. Nudist Beach

問題文

http://codeforces.com/contest/553/problem/D

解法

二分探索して BFS で解ける。
最大化したい値を例えば仮に x とおく。
最初、使える集合 S には k 頂点以外のすべての頂点を入れておく。
queue には使えなくなった頂点（初期は k 頂点）を入れる。
(隣接頂点のうち S に含まれる個数) / (次数) が x 未満となる頂点は、その後どうあがいても使えない。
したがって、queue から使えなくなった頂点を取り出して隣接頂点の次数を1つ下げ、この時 x 未満になったら、queue に追加する、ということを繰り返すだけで解ける。
まだ使える頂点が残っていればそれが答え S の候補である。

実装によるが、コーナーケースとして x の最大値が 0 の場合がある。
答えの集合が 0 なら k 個以外の頂点を全部入れるか、二分探索の下界を負の値にしておくとよい。
計算量は O(nlogm)

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, k; cin >> n >> m >> k;
    vector<bool> used(n);
    for(int i = 0; i < k; ++i) {
        int v; cin >> v;
        used[v - 1] = true;
    }

    vector<vector<int>> g(n);
    vector<int> deg(n);
    for(int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
        deg[a - 1]++, deg[b - 1]++;
    }

    auto check = [&] (double x) mutable {
        queue<int> que;
        auto cur = deg;
        auto erased = used;
        for(int i = 0; i < n; ++i) {
            if(erased[i]) que.push(i);
        }
        while(!que.empty()) {
            const int v = que.front(); que.pop();
            for(auto adj : g[v]) {
                if(erased[adj]) continue;
                if(--cur[adj] < x * deg[adj]) {
                    erased[adj] = true;
                    que.push(adj);
                }
            }
        }
        vector<int> res;
        for(int i = 0; i < n; ++i) {
            if(!erased[i]) res.push_back(i + 1);
        }
        return res;
    };

    vector<int> ans;
    double lb = -1, ub = 2e5;
    for(int lp = 0; lp < 60; ++lp) {
        const auto mid = (lb + ub) / 2;
        auto tans = check(mid);
        if(tans.empty()) {
            ub = mid;
        } else {
            lb = mid;
            ans = move(tans);
        }
    }

    const int r = ans.size();
    cout << r << endl;
    for(int i = 0; i < r; ++i) {
        cout << ans[i] << " \n"[i + 1 == r];
    }
}

感想

AGC 027 C と考え方が全く同じ。