GraphAndPairs [SRM721 Div1 Med]

問題概要

以下の条件を満たす無向グラフを作れ
1. グラフはシンプル
2. 3～1000頂点
3. 辺は2～1000本
4. 良いペア(最短距離がd)が丁度k通りある
2 <= d <= 50
1 <= k <= 5 * 10^4

解法

まず全体として連結でなくてもいいと言うのが重要なこと。
あとは、D=5なら

0 - 1 - 2 - 3 - 4 - 5

の両端に頂点を増やして

6-|               |-8
0 - 1 - 2 - 3 - 4 - 5
7-|               |-9

のようにしていくことで、組み合わせを増やしていく。
しかし、D=2ではスターの形となり、組み合わせ数の数え方が違ってくるので、ここは場合分けして考える。

D=2の時(d2関数)
中心に1つ周りがp頂点の時の組み合わせ数はp*(p+1)/2となるので、これを貪欲に作っていく。
kを超えずに最大の組み合わせ数となるpを見つけて、それをどんどん作っていけばいい

D!=2の時(other関数)
長さdのパスを作り、両端にp個の頂点を配置するとすると、組み合わせ数はp^2となるので、これを貪欲に作っていく。
これも、kを超えずに最大の組み合わせ数となるpを見つけて、それをどんどん作っていけばいい

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std;

vector<int> d2(int k) {
    int index = 0;
    vector<pair<int, int>> e;
    while (0 < k) {
        int p = 1;
        while (p * (p - 1) / 2 <= k) p++;
        p--;

        int cent = index;
        index++;
        rep(i, 0, p) {
            e.push_back({ cent, index });
            index++;
        }
        k -= p * (p - 1) / 2;
    }
    vector<int> res;
    res.push_back(index);
    fore(p, e) {
        res.push_back(p.first);
        res.push_back(p.second);
    }
    return res;
}
vector<int> other(int d, int k) {
    int index = 0;
    vector<pair<int, int>> e;
    while (0 < k) {
        int p = 1;
        while (p * p <= k) p++;
        p--;

        int top = index + 1;
        rep(i, 0, d) {
            e.push_back({ index, index + 1 });
            index++;
        }
        int last = index - 1;
        index++;

        rep(i, 0, p - 1) {
            e.push_back({ index, top });
            index++;
        }

        rep(i, 0, p - 1) {
            e.push_back({ index, last });
            index++;
        }

        k -= p*p;
    }

    vector<int> res;
    res.push_back(index);
    fore(p, e) {
        res.push_back(p.first);
        res.push_back(p.second);
    }
    return res;
}
struct GraphAndPairs {
    vector <int> construct(int d, int k) {
        if (d == 2) return d2(k);
        return other(d, k);
    }
};