Petya and Catacombs [Codeforces Round #445 Div1 A]

http://codeforces.com/contest/889/problem/A

N+1個の配列Tがある。
T[0] = 0で他は与えられている。
この時、以下の条件を満たす配列Aを構築する。

• N + 1個の要素から成る
• 全てのiについて i < A[i]
• あるiについてA[i] = A[j]を満たす最大のjがあるなら、T[i] = jである
  • つまり、A[i]と同じ数が左側にあるなら、最も近く同じ数の要素の添字がT[i]となっている
  • 同じ数が無いならT[i]は適当な値

こうして作れる配列Aの最大値を最小化し、その最小値を答えよ。

解法

Submission #32280626 - Codeforces
　
最大値を最小化するので、二分探索っぽいが、貪欲法で解ける。
後ろから以下のルールで要素を決定していく。
　
i番目の配列Aを確定するとする。

• まだ数が確定していないなら、A[i]に新しい数xを入れる(xはインクリメントして、次の数にしておく)
• T[i]が遷移先となるので、遷移先がまだ空っぽであれば、そちらにA[i]を入れる

これを繰り返すと、最大値を最小化できる。
　

int N, T[201010];
int A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N; rep(i, 1, N + 1) cin >> T[i];
    
    int x = 1;
    rrep(i, N, 1) {
        if (A[i] == 0) A[i] = x, x++;
        if(A[T[i]] == 0) A[T[i]] = x;
    }

    int ans = x - 1;
    cout << ans << endl;
}