AGC009 B問題 Tournament - 輪郭をなぞるだけのブログ

atcoder.jp

【問題の概要】
番号1から番号Nの人がいて、トーナメントで番号1の人が優勝した。番号2から番号Nの人に関しては、どの番号の人に負けたかという情報が与えられる。この情報と矛盾を生じないトーナメントで、その深さが最小であるときの深さを出力せよ。ここで、深さとは、構成されたトーナメントにおいて、優勝するのに必要な各人の試合数を比較したときの最大値のことである。

【考察】
とは言っても考察できるほどの力は持ち合わせていないので、いろいろ見ながらやっていた。
これだけでほとんど今日が消えた…

結論から言うと木DPを用いて問題を解く。
DP全然分かってないので困る。
どう遷移させるかとかを表現するのが自力でできない。

それはそうとして、以下のような手順を踏む。
1. 入力で与えられる情報を根付き木で表現する。
2. 遷移を把握して $dp$ 値を求める。(結論から書くと、 $dp[v] = \max\{dp[v'_i] + i | i = 1, 2, ..., k\}$ となる。)

まずは、入力で与えられる情報を木に落とし込む。
$v_1$ : 勝ち、 $v_2$ : 負けという情報が与えられる (入力では $v_1$ のみが順に与えられる。) 度に、 $v_1$ を親、 $v_2$ を子として辺の情報を格納しておく。(解説pdfとは逆向き。)

この根付き木 (根は頂点1) において、
$dp[v]$ := 頂点 $v$ を根とした部分木 (Tとする) 内での深さの最小値
と定義すると、求める値は $dp[1]$ である。

では、 $dp$ の値をどのように子ノードから伝播させていくか。
頂点 $v$ が $k$ 個の子ノード ( $v'_1$ , $v'_2$ ,..., $v'_k$ ) を持つとする。
f:id:OutLine:20191130214526p:plain
これをトーナメント表に対応させた一例としては、以下の図のようになる。( $k=3$ , 子ノードを根とした部分木はテキトーに書いている。)
f:id:OutLine:20191130231447p:plain
今見ている部分木T上で深さが最小となるようにトーナメント表をうまく構築できたとき、 (子ノードを根とする部分木の深さ) + (その深さが子ノードの中で何番目に大きいか) の最大値が、部分木Tでの深さの最小値となる。
この処理を行うために、すべての子ノードの $dp$ 値を取得してから、降順にソートしておく。( $dp[v'_1]\geq dp[v'_2]\geq ... \geq dp[v'_k]$ となるようにうまく $(v'_1, v'_2, ..., v'_k)$ を設置していくイメージ。)
ソート済みの値を順に見ていき、 $\max\{dp[v'_1]+1, dp[v'_2]+2, ..., dp[v'_k]+k\}$ を $dp[v]$ にする。
つまり、 $dp[v] = \max\{dp[v'_i] + i | i = 1, 2, ..., k\}$ となる。

正直なところ、この部分は文章で見ると分かりにくいと思うので、サンプルケースなどで、実験してみると分かりやすいかもしれない。
というか、あまり理解できなくて長い時間詰んでた。
数学や算数はできないので、証明はご容赦ください…

$dp$ 値は再帰で求めた。
今回はメモ化をする必要がない。

ソースコードは以下のようになった。
最近、変数が分かりにくいという指摘を受けたので、少しだけ気を付けてみた。
頂点とかは結構u, vで済ませてしまう。
depthは何を修飾すればよいのか分からなかったのでそのままだが…
0-indexedとしているので、上記の添え字との誤差を正しておく。

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

vector<int> graph[100005];  // 木の情報を格納

int dfs(int parent){
    if(graph[parent].size() == 0)    return 0;

    vector<int> depth;  // 親ノードparentの子ノードの部分木の深さ
    for(int i = 0; i < (int)graph[parent].size(); ++i){
        int child = graph[parent][i];
        depth.push_back(dfs(child));
    }
    sort(depth.begin(), depth.end(), greater<int>());

    int ret = 0;
    for(int i = 0; i < (int)depth.size(); ++i){
        ret = max(ret, depth[i] + i + 1);
    }

    return ret;
}

int main(){
    int n;
    cin >> n;
    for(int i = 1; i < n; ++i){
        int a;
        cin >> a;
        --a;
        graph[a].push_back(i);
    }

    cout << dfs(0) << endl;
}

【所感】
DPつよつよの民になりたい…

はてなブログ初心者なので、記法とかごちゃごちゃだが、また改善していきたいと思う。
そもそも更新を続けるかどうかという問題もあるのだが。
この問題に時間を取られすぎてやる気を吸い取られたため、この記事を書いたところもあるので。
虚無な時期よりは幾分マシにはなっているとは言え、大学院すっぽかしすぎでは。
研究と両立できる日はいつになるのだろうか…