【競プロ精進日記】c++習得編＜２０＞Beginaid

本記事は管理人が競技プログラミングを始めたため，その精進日記としてログを取ったものです。アウトプットして積極的にモチベーションを上げていく作戦です。まずはc++を習得するところから始めます。その他の記事は以下をご覧ください。

内容は管理人の推測や恣意的な感想を大いに含みます。もし間違い等ありましたらご指摘ください。あくまでも参考程度にお願い致します。

【競プロ精進日記】目次まとめ ABC Atcoder Beginner Contestの過去問を解いています。最低限のコメントと一言が添えられています。 ...

再帰関数

C++入門 AtCoder Programming Guide for beginners (APG4b)を1からさらっていく内容です。

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

int count(vector<vector<int> > &C, int x){
  if (C[x].size()==0){
    return 1;
  }
  int report = 0;
  for (int c: C[x]){
    report += count(C, c);
  }
  report += 1;
  return report;
}

int main() {
  int N = 0;
  cin >> N;
  vector<int> P(N);
  P[0] = -1;
  rep(i, N-1){
    cin >> P[i+1];
  }
  vector<vector<int> > C(N);
  rep(i, N-1){
    int parent = P[i+1];
    C[parent].push_back(i+1);
  }
  rep(i, N){
    cout << count(C, i) << endl;
  }
}

難しいです！再帰関数は競プロを始めて最初にぶち当たる壁だと思います。再帰の数が少ない場合や規則的な場合（フィボナッチ数列など）には，実際に実行手順を思い浮かべながらコーディングすることができます。

しかし，今回のように各ノードの子がいくつあるかわからない状況などでは，実際にイメージすることは難しいです。そのような意味で，再帰関数を実装する際には抽象的に「再帰」という概念を扱っていく必要がありそうです。

今回引っかかったのは，またまた添字です。0始まりなのか，1始まりなのか。そして，与えられる入力の長さがN-1であるということも忘れていました。また，再帰関数で返り値を指定せずにエラーで怒られてしまうこともありました。優秀なvscode君は赤い波線で「返り値にintを指定している関数だけどreturnが書いてないよ」と教えてくれるので助かります。

配列への追加がpush_backである点もこれから慣れていかなくてはなりません。また，再帰関数が参照渡しであるのはメモリの節約であると認識しています。