ブログ名

競技プログラミングやお歌のお話をする高菜です。

eduf.43 D - Degree Set 解説

問題へのリンク

https://codeforces.com/contest/976/problem/D

解法

 1 項以上の正の整数の列  0 \lt d_1\lt d_2 \lt \dots \lt d_n-1 に対して,、 d _ { n - 1 } + 1 頂点のグラフ  f( d _ 0, \dots, d _ {n - 1 } )  をいい感じに定義して、これが問題の答えになるようにがんばります。

まず、 n = 1 のときには、完全グラフ  f ( d ) = K ^ { d + 1 } とすると良いです。

また、 n = 2 のときには、完全グラフと離散グラフの間をすべての辺で結んだもの  f( d, e ) = K ^ { d + 1 } * { \rm discrete } ( e - d ) とすると良いです。

最後に、 3 \le n のときには、 n - 2 の場合に帰着です。 f ( d _ 0, \dots d _ { n - 1 } ) = \left ( f ( d_ 1 - d _ 0, \dots, d _ { n - 2 } - d _ { n - 0 } ) \sqcup { \rm discrete } ( d _ { n - 1 } - d _ { n - 2 } ) \right ) * K ^ { d _ 0 } とすると良いです。

実装

入力です。問題の  Nm にして、頂点数の方を n と書きました。

usize m;
std::cin >> m;
vec<usize> d(m);
for (usize& x: d) std::cin >> x;
usize n = d.back() + 1;

隣接行列を定義です。こちらに答えが入ります。

auto adj = mkvec<2, usize>(n, n);

完全グラフと完全二部グラフを簡単に追加できるようにしておきましょう。

auto complete = [&](usize l, usize r) {
    for (usize i=l; i<r; i++) for (usize j=i+1; j<r; j++) {
        adj.at(i).at(j) = true;
    }
};
auto complete_bipatite = [&](usize l0, usize r0, usize l1, usize r1) {
    for (usize i=l0; i<r0; i++) for (usize j=l1; j<r1; j++) {
        adj.at(i).at(j) = true;
    }
};

準備は整いました。グラフを小さくしていきます。

while (!d.empty()) {
    if (d.size()==usize{1}) {
        complete(0, d.at(0) + 1);
        break;
    } else if (d.size()==usize{2}) {
        usize c = d.at(0);
        usize r = d.at(1) + 1;
        complete(0, c);
        complete_bipatite(0, c, c, r);
        break;
    } else {
        usize x = d.at(0);
        usize r = d.back() + 1;
        usize c = r - x;
        complete(c, r);
        complete_bipatite(0, c, c, r);
        for (usize& z: d) z -= x;
        d.erase(d.begin());
        d.pop_back();
    }
}

最後に出力で辺リストに変換をして、添字を 1 - based にすると出来上がりです。

vec<diag_pair<usize>> ans;
for (usize i=0; i<n; i++) for (usize j=i+1; j<n; j++) if (adj.at(i).at(j)) {
    ans.emplace_back(i, j);
}
std::cout << ans.size() << '\n';
for (auto&& p: ans) {
    std::cout << p.first + 1 << ' ' << p.second + 1 << '\n';
}

editorial を拝読いたしました。

Educational Codeforces Round 43 Editorial - Codeforces

どうやら項数 0 を認めることで少し簡単になるようです。