SRM 680 div1 med: BearSpans - mayoko’s diary

問題

解法

1 回の操作で必ず component の数が半分以下になります。
また, sample 1 のように, 「あと 1 回で操作をやめたい」と思ったら, component のひとつ目の要素と, 他の component を小さい辺で結べば終わります。

これらのことを考えると,

K がでかすぎるとどうしてもそれ以下の回数でアルゴリズムが終わってしまうので NG

そうでない時は, K-1 回はトーナメントっぽく頂点をつないでいく
- 今考えている component の集合が now という配列で表されるとして, now[2*i], now[2*i+1] をつないでいく

あと 1 回でアルゴリズムが終了しないといけないので, now[0] と now[i] (i > 0) をつなげる

それでも辺の数が余ったら, まだ貼ってないところに辺を貼っていく(これはグラフ構成に影響を与えない)

bool used[1010][1010];

class BearSpans {
public:
    vector <int> findAnyGraph(int N, int M, int K) {
        const vector<int> no = {-1};
        {
            int tmp = N, k = 0;
            while (tmp>1) {
                tmp /= 2;
                k++;
            }
            if (k < K) return no;
        }
        vector<int> now, ans;
        for (int i = 0; i < N; i++) now.push_back(i);
        for (int i = 0; i < K-1; i++) {
            vector<int> next;
            int size = now.size();
            for (int j = 0; j < size/2; j++) {
                ans.push_back(now[2*j]);
                ans.push_back(now[2*j+1]);
                next.push_back(now[2*j]);
            }
            if (size%2) {
                ans.push_back(now[size-2]);
                ans.push_back(now[size-1]);
            }
            now = next;
        }
        int size = now.size();
        for (int i = 1; i < size; i++) {
            ans.push_back(now[0]);
            ans.push_back(now[i]);
        }
        memset(used, false, sizeof(used));
        size = ans.size();
        for (int i = 0; i < size/2; i++) {
            used[ans[2*i]][ans[2*i+1]] = true;
            used[ans[2*i+1]][ans[2*i]] = true;
        }
        if (M < size/2) return no;
        int cur = size/2;
        for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) {
            if (!used[i][j] && cur < M) {
                ans.push_back(i);
                ans.push_back(j);
                cur++;
            }
        }
        for (int& el : ans) el++;
        return ans;
    }
};