AtCoder Grand Contest 009 B - Tournament

問題

　人でトーナメントを行い1番目の人が優勝した。2から番目の人が誰に負けたかを与えるのでトーナメントの深さとして最小の値を求めよ。

解法

　番目の人がの人に勝ったとして、それぞれの対戦カードの下に位置する部分トーナメント木の深さをとすると、これらに対して好きなようにを足したものについて最小の値が答えになる。それはdfsで実装すれば簡単。

　見にくいけれど考察中のメモの方が分かりやすそう。

感想

　800点問題ということでかなり身構えたが考察が一発で正しい方向に向かってくれたおかげで20分程度しかかからなかった。計算量も間に合うのかどうかよくわからないままの提出だったが47msなので全く問題はなかった。

　解説PDFを読むと木DPということが書いてある。DPという感覚はなかったので驚いてしまったが、やっていることは同じ。むしろこれがDPという感覚が湧いてこなかった方が少し問題にも思えるが、無意識にできたということで良かったとも言えるのかもしれない。

　一番最初はNode構造体と作ってどうのこうのということを考えたりしていたので、それは流石に見当違いという感じだった。木を見たときに上手く再帰的な性質を見抜いて実装するということを自然に思い浮かぶようになれればいいと思う。後は点数を見てビビらないっていうのが大事ですね。

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

vector<vector<int>> loser;

int dfs(int curr) {
    if (loser[curr].empty()) {
        return 0;
    }

    vector<int> nums;
    for (int l : loser[curr]) {
        nums.push_back(dfs(l));
    }
    sort(nums.begin(), nums.end(), greater<int>());
    for (int i = 0; i < nums.size(); i++) {
        nums[i] += (i + 1);
    }

    return *max_element(nums.begin(), nums.end());
}

int main() {
    int N;
    cin >> N;
    vector<int> a(N, 0);
    loser.resize(N);
    for (int i = 1; i < N; i++) {
        cin >> a[i];
        a[i]--;
        loser[a[i]].push_back(i);
    }

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