Atcoder AGC #009 B. Tournament

B: Tournament - AtCoder Grand Contest 009 | AtCoder

解いたあとに解説見たらDPでごにょごにょって書いていたが、もっとわかりやすくあっさり書けた。

n人の人が、負けたらそこで終わりのトーナメント形式で優勝を目指して戦う。番号１の人が優勝したことはわかっており、他の人が誰に負けたかという情報も与えられる。ありうるトーナメントの形のうち、深さの最小値を求める問題。まず番号１を根として、AがBに勝ったという情報から、AからBに子をつくるように木を構成してみる。そこからトーナメントの形を構成しようと考えると、相異なる親をもつ葉を同時にコスト１で削除していく操作を繰り返すことで、根以外のノードをすべて削除するまでにかかるコスト、が求める最小値に一致することが証明できる。あるノードを親としてその複数の子ノードについて考える。それら以下のノード全てを削除するためのコストはわかっているものとしてよい。それが例えば、1, 1, 1だったとすると、コストは親を削除するコストを除いて3になる。なぜなら、削除の操作は親ノードが一致する場合は同時に行えないので、１つずつ削除するしかないからである。同様に、コストが1, 2, 3である場合も3になることがわかる。なぜなら、１回目の操作でコストは0, 1, 2になり、２回目の操作で0, 0, 1になり、3回目の操作で0, 0, 0になるからである。結局、あるノードのコストがxであることを、そのノードはx秒後以降に削除できる、という条件に読み替えて、全てのノードを削除するのに何秒かかるかという問題に帰着できる。これは昇順にソートして、貪欲に調べて行くことができる。計算量はソートの部分が一番大きく、O(nlogn)。

#include "bits/stdc++.h"
using namespace std;
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define all(x)                (x).begin(), (x).end()

vector<int> g[101010];

int dfs(int s) {
        int res = 0;
        vector<int> v;
        for (auto ns : g[s]) v.push_back(dfs(ns));
        sort(all(v)); //削除コスト順にソート
        rep(i, v.size()) res = max(res + 1, v[i]);  //小さいものから見ていき、今見ているノードか、時刻＋１の大きい方をとる
        return res + 1; //親ノードを削除するコストを足す
}

signed main() { 
        int n;
        cin >> n;
        rep(i, n - 1) {
                int a;
                cin >> a;
                a --;
                g[a].push_back(i + 1);
        }
        cout << dfs(0) - 1 << endl;
        return 0;
}

AGCのB問題はすべて埋めたので、次はC問題を埋めていく。