質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
87.20%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

解決済

Atcoder EX20 報告書の枚数 解答例の疑問点について

thxya1
thxya1

総合スコア3

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

1回答

0評価

1クリップ

141閲覧

投稿2022/06/23 06:48

Atcoder EX20 報告書の枚数の解答例について、疑問点が2つあり質問させていただきました。

EX20 報告書の枚数

問題文

あなたはA社を経営する社長です。 A社はN個の組織からなり、それぞれに0番からN−1番の番号が付いています。 0番の番号が付いた組織はトップの組織です。

組織間には親子関係があり、0番以外のN−1個の組織には必ず1つの親組織があります。 子組織は複数になることがあります。 また、それぞれの組織は直接的または間接的にトップの組織と関係があるものとします。

あなたは全ての組織に報告書を提出するように求めました。 混雑を避けるために、「各組織は子組織の報告書がそろったら、自身の報告書を加えて親組織に渡す」ことを繰り返します。 子組織が無いような組織はすぐに親組織に報告書を渡します。 トップの組織は子組織の報告書がそろったら、自身の報告書を加えて社長に提出します。

それぞれの組織が1枚の報告書を提出します。

各組織について、「その組織が親組織に提出することになる報告書の枚数」を出力するプログラムを作成してください。 ただしトップの組織については「社長に提出する報告書の枚数」を出力してください。

以下解答例

#include <bits/stdc++.h> using namespace std; // x番の組織が親組織に提出する枚数を返す // childrenは組織の関係を表す2次元配列(参照渡し) int count_report_num(vector<vector<int>> &children, int x) { // ベースケース if (children.at(x).size() == 0) { // 子組織から受け取ることは無いので1枚であることが確定している return 1; } // 再帰ステップ int sum = 0; for (int c : children.at(x)) { sum += count_report_num(children, c); } sum += 1; // x番の組織の報告書の枚数(1枚)を足す return sum; } // これ以降の行は変更しなくてよい int main() { 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); } // 組織の関係から2次元配列を作る vector<vector<int>> children(N); // ある組織の子組織の番号一覧 for (int i = 1; i < N; i++) { int parent = p.at(i); // i番の親組織の番号 children.at(parent).push_back(i); // parentの子組織一覧にi番を追加 } // 各組織について、答えを出力 for (int i = 0; i < N; i++) { cout << count_report_num(children, i) << endl; } }

疑問点はこの解答例の6行目にある

int count_report_num(vector<vector<int>> &children, int x) {

と再帰ステップから3行下の

sum += count_report_num(children, c)

この2点です。

まず、

int count_report_num(vector<vector<int>> &children, int x) {

この部分は何を示しているのでしょうか。

また、

sum += count_report_num(children, c)

の count_report_num(children, c)は何を示しているのでしょうか。解釈としてはchildrenのc番目の枚数をsumに足すと考えていますが、解釈が誤っている可能性があり質問させていただきました。

再帰関数を最近学び始めたばかりで初歩的な質問かと思いますが、教えていただけると嬉しいです。
ご回答、よろしくお願いします。

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

まだ回答がついていません

会員登録して回答してみよう

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
87.20%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。