AtCoder ABC 263 B問題

B問題で解けなかったので、茶色コーダーまでまだまだですね…他の方のコードを参考にして、まとめました。

入力と結果の例

例１

5
1 2 3 4

という入力があったとすると、　

2の親は1
3の親は2 → 2の親は1
4の親は3 → 3の親は2 → 2の親は1
5の親は4 → 4の親は3 → 3の親は2 → 2の親は1

=>　1は5の4代祖先に当たるので、4を出力

例2

5
1 2 2 3 

という入力の場合、

2の親は1
3の親は2 → 2の親は1 -b
4の親は2 → 2の親は1
5の親は3 → 3の親は2 → 2の親は1　-a

=> 1はの5の3代祖先に当たるので、3を出力

ということです。

考え方

前の結果が次の結果に影響してくるのでダイナミックプログラミング(dp)を使います。
上の例２からわかると思いますが、aの結果を求めるときに、bの結果を使っていますよね。

どのようにしてdpを使うかですが、

例１でやってみます。

まず何代前かを表すdp配列を持っておきます（０で初期化）。左から、人1,2,3,4,5がそれぞれ人１の何代祖先かを表しています。
dp = [0, 0, 0, 0, 0]
人1は人１の０代祖先なので、0のままにしておきます。
dp = [0, 0, 0, 0, 0]
次に、人2は人１の1代祖先なので、前の結果(0代祖先の)の１代祖先に当たるので、
dp = [0, 1, 0, 0, 0]
次に、人3は人2の1代祖先なので、前の結果(1代祖先の)の１代祖先に当たるので、
dp = [0, 1, 2, 0, 0]
繰り返していくと
dp = [0, 1, 2, 3, 4]
になり、この配列の最後の４は、人1は人5の4代祖先と言うことを表しているので、これを出力します。

例2でやってみます。

人1は人１の０代祖先なので、0のままにしておきます。
dp = [0, 0, 0, 0, 0]
次に、人2は人１の1代祖先なので、前の結果(0代祖先の)の１代祖先に当たるので、-c
dp = [0, 1, 0, 0, 0]
次に、人3は人2の1代祖先なので、前の結果(1代祖先の)の１代祖先に当たるので、-d
dp = [0, 1, 2, 0, 0]
次に、人4は人2の1代祖先なので、前の結果(1代祖先の)の１代祖先に当たるので、 <= 前の結果は -c です。
dp = [0, 1, 2, 2, 0]
次に、人5は人3の1代祖先なので、前の結果(2代祖先の)の１代祖先に当たるので、 <= 前の結果は -d です。
dp = [0, 1, 2, 2, 3]
になり、この配列の最後の3は、人1は人5の3代祖先と言うことを表しているので、これを出力します。

頭がこんがらがりそうです。

ではコードに移りましょう。

コード

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

int main(){
  int n;
  cin >> n;
  vector<int> vec(n+1);
  vector<int> dp(n+1);
  for(int i=1; i<n; i++){
    cin >> vec.at(i);
    vec.at(i)--;
  }
  dp.at(1) = 0;
  for(int i=1; i<n; i++) dp.at(i) = dp.at(vec.at(i)) + 1;
  cout << dp.at(n-1) << endl;
  return 0;
}

下の部分は上で、解説した部分をコードに直しただけなので、説明を省きます。
vecと言う配列は何をしているのかというと、前の結果を示すインデックスを表しています。

上の例でいうと、
「次に、人2は人１の1代祖先なので、前の結果(0代祖先の)の１代祖先に当たるので、」
の「人１の」の部分です。この部分は　入力値と一致します。今回は、インデックスに対応させたいので、入力値を-1したものを前の結果が格納されたdpのインデックスを示すものとして用いています。

最後に

B問題で解けなかったのは本当に悔しいです。自分はまだ灰色コーダーなので、茶色を目指して頑張ります。
間違いなどあれば、指摘していただけると嬉しいです。