初見時は証明なしに再帰的にやった...

問題概要

$N$ 頂点の完全グラフがあたえられる。
このグラフの辺に、非負整数値を付けていく方法のうち

整数値が等しい辺のみからなる部分グラフが奇数長のサイクルを含まない

という条件を満たす範囲内で、付けられた非負整数値の最大値として考えられる最小値を求めよ。またそのような解を具体的に一つ復元せよ。

制約

$2 \le N \le 500$

考えたこと

こういうのは、とりあえず小さい $N$ で実験してみるのがよさそう。

$N = 2$ では明らかに 1 でよい。
$N = 3$ は二色必要になる。 $N = 4$ も二色で OK。
$N = 5$ はあれこれやってると、どうやっても三色必要に思える。

直感的に考えたこと

奇数長のサイクルを含まない、というのは二部グラフであることと同値である。これはすごく有名事実で何度も何度も登場する概念となっている。で、 $N = 5$ のグラフを「頂点数 3」(左側) と「頂点数 2」(右側) とに分けてみる。

そうすると左右の間の辺は長さ 1 で埋めて、左側頂点同士を結ぶ辺や、右側頂点同士を結ぶ辺は長さ 2 以上で埋める必要が出てくる。そして、左側頂点が 3 個あるので、長さ 3 の辺も必要になってくる。

これを一般化して考えると、 $N$ の問題は $N/2$ の問題に帰着できて...という風に考えられる。 $N = 2^{k}$ のときは $k$ 色必要ということになる。

...これではまだ証明にはなっていない。けど、いかにもそれっぽいので出すと通る。

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<vector<int> > res;

void rec(int left, int right, int v) {
    if (right - left <= 1) return;

    // 再帰的に
    int mid = (left + right) / 2;
    rec(left, mid, v+1);
    rec(mid, right, v+1);

    // 二部グラフの中間部分を埋める
    for (int i = left; i < mid; ++i) {
        for (int j = mid; j < right; ++j) {
            res[i][j] = v;
        }
    }
}

int main() {
    cin >> N;
    res.assign(N, vector<int>(N, 1));
    rec(0, N, 1);

    for (int i = 0; i < N; ++i) {
        for (int j = i+1; j < N; ++j) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
}