ひらめの日常

日常のメモをつらつらと

AtCoder: 第一回日本最強プログラマー学生選手権-予選- D Classified (600)

問題はこちら

atcoder.jp

今回はほぼ解説放送と解説ブログを参考にした自分用のメモ。

考え方

JSC2019予選 - D 「Classified」 (600) - Mister雑記

[AtCoder 参加感想] 2019/08/25:JSC2019予選 | maspyのHP

  • 奇閉路が存在しないようにグラフを分割できれば良い。
  • 奇閉路が存在しないことは、二部グラフが構成できることと同値。
  • よって、完全グラフを二部グラフに分割することを考える。
  • なるべくたくさんの辺を取り除いていきたいので、最大の完全二部グラフを取り除いていくことを考える。
  • 完全グラフから完全二部グラフを取り除いていくと、残りの部分グラフはそれぞれ完全グラフを構成している。
  • よって、再帰的に完全グラフから完全二部グラフを構成していくことを繰り返せば良い。

解答

ほぼ写経コード。

残っている頂点を半分ずつに分割して、完全二部グラフを構成していく。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;

int main() {
    ll n;
    cin >> n;

    vvl level(n, vl(n));
    auto dfs = [&](auto &&f, ll l, ll r, ll lev) -> void {
        if (l + 1 == r) return;
        ll mid = (l + r) / 2;
        for (ll i = l; i < mid; ++i) {
            for (ll j = mid; j < r; ++j) {
                level[i][j] = lev;
            }
        }
        f(f, l, mid, lev + 1);
        f(f, mid, r, lev + 1);
    };
    dfs(dfs, 0, n, 1);
    for (ll i = 0; i < n - 1; ++i) {
        for (ll j = i + 1; j < n; ++j) {
            cout << level[i][j] << ' ';
        }
    }
    return 0;
}