Mister雑記

競プロやります。

JSC2019予選 - D 「Classified」 (600)

atcoder.jp

問題

 N頂点完全グラフの各辺に対して、以下を満たすように正整数を割り当てる。

  • 頂点 vと正整数 Lを任意に取る。
  •  vから Lが割り当てられた辺のみを辿って vに戻るとき、そのパスの長さは常に偶数。

このような割り当てで、割り当てられる正整数の最大値が最小のものを出力せよ。

制約

  •  2 \leq N \leq 500

考察

まず条件を分かりやすいように言い換えると、

  • 任意の正整数 Lについて、 Lが割り当てられた辺による誘導部分グラフが二部グラフをなす。

となる。「奇数長の閉路を持たない」と「二部グラフである」が同値であることが肝。

まず1を割り当てる辺を決める。 極力辺を使った方が後々楽なので、辺数が最多となる割り当てがしたい。 そのような割り当てが何かと考えると、これは N頂点を半々に分割した完全二部グラフとなる。

次に2を割り当てるが、残った辺に注目するとこれは2つのクリークをなしている。よってこれらに再帰的に上と同じ割り当てをしてやればいい。

1つの正整数を割り当てる度に頂点数が半減するので、最大値は \lceil \log_2 N \rceilになる。 最小性の証明は思いつかなかったが、まぁ最適だろうと直感を信じて投げたら通った。

実装例

atcoder.jp

using namespace std;

int main() {
    int N;
    cin >> N;

    vector<vector<int>> ans(N, vector<int>(N, -1));

    // 頂点集合[l, r)からなるクリークにd以上を割り当てる
    function<void(int, int, int)> dfs =
        [&](int l, int r, int d) {
            if (r - l <= 1) return;

            int m = (l + r) / 2;
            // [l, m)と[m, r)に分割して完全に部グラフを構築
            for (int i = l; i < m; ++i) {
                for (int j = m; j < r; ++j) {
                    ans[i][j] = d;
                }
            }

            dfs(l, m, d + 1);
            dfs(m, r, d + 1);
        };
    dfs(0, N, 1);

    for (int v = 0; v < N; ++v) {
        for (int u = v + 1; u < N; ++u) {
            cout << ans[v][u] << " ";
        }
        cout << endl;
    }
    return 0;
}