JSC2019予選 D - Classified (600)

問題

頂点の完全グラフの全ての辺に以下を満たすように正の整数値(=レベル)を割り当てる
- 頂点 $i$ からレベルが等しい通路のみをいくつか通って $i$ に帰ってくるとき、その経路長は必ず偶数になる
上のような割り当て方のうち、レベルの最大値を最小化するものを出力せよ
$2 \leq N \leq 500$

考察

出発した頂点に戻るような全ての経路の長さが偶数、ということはすなわち奇数長の閉路がないということになる。「奇数長の閉路がない」 $\Leftrightarrow$ 「二部グラフである」ということに気づくと、二部グラフをいくつか組み合わせて完全グラフを作る問題に読み替えられる。

ここで少し悩んだので一旦実験してみることにした。

$N=5$ でとりあえず $A:[1, 2, 3$ ]と $B:[4, 5$ ]の二部に分け、その二部グラフに含めることができる全ての辺(=完全二部グラフの辺)をレベル1(赤色)とした(左図)。あとは残った辺についてレベル2以上の値を割り振っていきたいわけだが、ここで今レベルの決まった辺を削除してみると...(右図)

なんということでしょう！残っているのは頂点集合 $A, B$ それぞれの完全グラフではありませんか！！！考えてみると二部グラフの辺は $A$ の一頂点と $B$ の一頂点を結ぶものであるから、 $A$ 同士や $B$ 同士を結ぶ辺は全て残ってしまう(つまり完全)のでそれはそうという感じ。

ということで、二部グラフの辺のレベルを確定させたあとは再帰が使えそうだ。(この場合は $N=|A|=3$ と $N=|B|=2$ の時に再帰)

では $N$ が与えられた時に、頂点集合 $A, B$ はどのように分ければいいのか？これは直感通り半々に分けることが最適であると示せる。

まず頂点数 $N$ について題意の割り当て方によるレベル数の最小値を $L(N)$ とすれば、 $N=k$ の完全グラフは $N=k+1$ の完全グラフに丸ごと含まれることから、 $L(k) \leq L(k+1)$ が言えて、これにより $L(N)$ が広義単調増加であることがわかる。

このとき $N$ 個の頂点を $A, B$ のように分けた場合、レベル数は $\max (\; L(|A|),\;L(|B|) \; )$ であり、 $L$ が広義単調増加であることからこれは $L( \; \max( |A|, |B| ) \; )$ に等しい。よって $\max( |A|, |B| )$ を最小にする分け方が最適であり、これは $A, B$ を半分ずつ分けるということに他ならない。

以上から、

$1 \sim N$ を半数ずつ $A, B$ に振り分ける
$A, B$ 間の辺のレベルを1とする
$A, B$ それぞれについて再帰を適用する

という流れで実装すれば良さそう！

実装

あとは書くだけ！こういう考察さえすれば実装は軽い問題、結構好き。

using namespace std;

#define MAX_N 600

int a[MAX_N][MAX_N];  // a[i][j] = 辺i-jのレベル

// s <= i < e を満たす全ての頂点iからなる完全グラフについて、レベルを割り振る
void set_levels(int s, int e) {
    if (e - s < 3) return; // 頂点数3未満の場合、完全グラフ==二部グラフ
    int now = a[s][s], // 今のレベル
        m = (s + e) / 2;
    for (int i=s; i<m; i++)
        for (int j=s; j<m; j++)
            a[i][j] = now+1;
    for (int i=m; i<e; i++)
        for (int j=m; j<e; j++)
            a[i][j] = now+1;

    // 前半と後半に分けて再帰
    set_levels(s, m);
    set_levels(m, e);
}


int main() {
    int n;
    cin >> n;
    fill(a[0], a[n], 1); // 一旦全部1で埋める
    set_levels(0, n);
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            cout << a[i][j] << (j == n-1 ? '\n' : ' ');
        }
    }
    return 0;
}

atcoder.jp

shugo's kitchen

コンピュータサイエンスを美味しく調理していきたい

JSC2019予選 D - Classified (600)

問題

考察

実装