AtCoder「2.05.再帰関数」の例題

https://atcoder.jp/contests/apg4b/tasks/APG4b_v

入力は P1からP(N-1)までの配列 内容は 親の番号 で、 0はroot

1. 親子関係のグラフを作って、その階層の最大値を求めればよさそう。
2. 入力は配列のみO(n)なので、その後できるだけ少ない処理で済ませたい。
3. 子に行くほど数値が大きくなるとは宣言されていない。念ためソートして処理する方法以外を考える

アプローチ1

1. iを自身の番号とした配列を作り、子の値を vector<int> の値として入れていき処理しようと思う。理由はデータを処理しながら親番号を参照してそこに自分を入れられるから。
2. 完成した配列をどう処理するか？総なめしてDFSで深さを求めることになる。 +O(n)

アプローチ2

1. データ処理は1と同様
2. インデックス番号は親とした上で、格納するデータ型について、深さの最大値を入れていくのはどうか？データを入れる際にまず自身の値をインデックスとして参照し、存在したらその値に+1して値をセット。なければ1をセット(配列のデフォルトを0とすれば条件式を省ける)
3. 2のやり方でも、結局最後は総なめしなければならない +O(n)

結論

データの読み込みと処理

サンプルコードに記載されていた、データを取る処理（以下）はその過程で他の処理を行っておらず冗長だった。
自身は直感的にそれをわかっていて、「cinを読み込みながらデータを整理する」方法を取ったが、これは正解だった。

int N;
cin >> N;
vector<int> p(N);  // 各組織の親組織を示す配列
p.at(0) = -1;  // 0番組織の親組織は存在しないので-1を入れておく
for (int i = 1; i < N; i++) {
    cin >> p.at(i);
}

再帰関数の実装

はじめに実装したものは引数が余分だった。

初期の実装

int dfs(vector<vector<int>> &children, int x, int depth) {
    if (children.at(x).size() == 0) {
        return depth;
    }

    depth++;
    int max_depth = 0;
    for (int c: children.at(x))
    {
        max_depth = max(max_depth, dfs(children, c, depth));
    }

    return max_depth;
}

よりシンプルな実装 (第三引数は不要だった)

int dfs(vector<vector<int>> &children, int x) {
    if (children.at(x).size() == 0) {
        return 0;
    }

    int max_depth = 0;
    for (int c: children.at(x))
    {
        max_depth = max(max_depth, dfs(children, c));
    }

    return max_depth + 1;
}

なぜ余計な実装だったのか

• depth変数はベースケースに到達した際に同じ値を加工せず返している。
• depth++ するタイミングはfor文の手前でも帰り値を返すタイミングでも結果は変わらなかった。
• シンプルに考えれば、「 dfs() が呼び出された回数をカウント」すればよかった。
• つまり return 時にインクリメントすればそれで済んだ。
• 元の実装はDFSで降りていくときにカウントしていくので、「深さをカウントしたい」という気持ちが先行した結果、人間の直感的な実装になってしまったのだと思う。もう片方は登るときにカウントしている。

反省

今後はDFSでは上り下り両方の視点から考えるようにする。
慣れたら再帰の実装で頭のリソースを割くこと無く、もっと単純に考えるようにする（なると思う）