はじめに

最近、アルゴリズムの勉強として、アルゴ式に取り組んでいます。「アルゴリズム初級」の「再帰関数」に取り組んでいましたが、実装時に引っかかってしまったことがありました。初心者の大変初歩的なミスですが、メモがてら書き残しておきます。

引っかかった問題

部下の人数という問題です。

ある会社には N 人の社員がおり、0 から N−1 までの社員番号が振られています。
社員 0 以外の社員は自分より若い番号の社員のうち 1 人を直属の上司として持ちます。社員 i の直属の上司は Piです。
社員 X は何人の部下を持つか答えるプログラムを作成してください。ただし、「社員の部下の部下」のように直属でない部下も全て数えることとします。

グラフ構造を隣接リストで管理することにし、次のようなプログラムを書きました。

#include <bits/stdc++.h>
#define print(x) cout << x << endl;
#define rep(i, s, n) for (long long i = s; i < (long long)(n); i++)
#define INF 1010000000
using namespace std;
using ll = long long;

ll func(vector<vector<ll>> g, ll x)
{
  if (g[x].size() == 0) return 0;
  ll cnt = 0;
  rep (i, 0, g[x].size())
    cnt += func(g, g[x][i]);
  return cnt + g[x].size();
}

int main()
{
  ll N, X;
  cin >> N >> X;
  vector<vector<ll>> g(N);
  rep (i, 1, N)
  {
    ll p;
    cin >> p;
    g[p].push_back(i);
  }
  print(func(g, X));
  return 0;
}

サンプルケースは問題なく通過しましたが、一つのケースだけ「時間切れ」となってしまいました。

何が原因だったか

原因は、再帰関数の引数にありました。

...
ll func(vector<vector<ll>> g, ll x) 
{
...

二次元配列をそのまま渡しているため、関数が再帰するたびに毎回配列のコピーが発生していました。入力数が小さい時なら問題ありませんでしたが、入力数が大きい場合、コピーで時間が取られてしまっていたのです。

解決策

二次元配列の参照だけ渡すようにしました。これで無駄な配列のコピーが削減され、時間内に通過するようになりました。

...
ll func(vector<vector<ll>> &g, ll x) 
{
...

終わりに

普段は意識していなかった配列のコピーにも、計算機のコストがしっかりとかかっているのだと改めて認識しました。