AtCoder Grand Contest 009 B - Tournament

問題概要

略

リンク

やや雑な解法メモ

次のようなデータ構造を考える。

child[i] = [人iに負けた人たち] 

また、次のようなDPを考える。

DP[i] = 人iが勝ち進んだところまでのトーナメント表の最小の深さ

child[v] = [m1, m2, m3, m4]の時、 miを人vが直近に対戦した順にk1, k2, k3, k4とすると、vが勝ち進んだところまでのトーナメント表は次のようになる。

未定の部分は貪欲に決まる。 できるだけトーナメント表が浅くなるようにするためには、k1にmax(DP[mi]) (=トーナメント表が深いもの) を持ってきたほうがよいからである。 DP[mi]を降順にソートしたものを[d1, d2, d3, d4]とすると、max(di+i)がDP[v]になる。

これを深さ有線探索で再帰的に求める。

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++)
#define pb push_back
#define INF 1000000007LL
#define all(a) (a).begin(),(a).end()
 
typedef long long ll;
typedef pair<int,int> p;
 
int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};
 
#define MAX_N 100010
 
vector<int> child[MAX_N];
 
ll dfs(ll node){
    vector<int> v;
    for(auto ch: child[node]) {
        v.pb(dfs(ch));
    }
    sort(v.begin(),v.end(),greater<int>()); //N log N
    ll tmp=0;
    REP(i,v.size()){
        tmp=max(tmp,1+i+v[i]);
    }
    return tmp;
}
int main(){
    int N;
    cin>>N;
    REP(i,N-1){
        int a;
        cin>>a;
        child[--a].pb(i+1);
    }
    cout << dfs(0) << endl;
    
}