EX18 - 報告書の枚数 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

説明ページに戻る

問題文

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

組織間には親子関係があり、組織 0 以外の N - 1 個の組織にはそれぞれ 1 つの親組織が存在します。
組織 i\ (1 ≤ i ≤ N - 1) の親組織は組織 p_i です。
ここで、ある組織からその組織の親組織をたどることを繰り返すと、必ずトップの組織（組織 0）に到達します。

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

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

制約

  • 1 ≤ N ≤ 50
  • 0 ≤ p_i ≤ N - 1\ (1 ≤ i ≤ N - 1)
  • ある組織からその組織の親組織をたどることを繰り返すと、必ずトップの組織（組織 0）に到達する。
  • 入力される値はすべて整数である。

入力

入力は次の形式で標準入力から与えられます。

N
p_1 p_2 p_3 \ldots p_{N - 1}

組織 0 はトップの組織であり、親組織が存在しないことに注意してください。

出力

\text{ans}_0
\text{ans}_1
\text{ans}_2
\vdots
\text{ans}_{N - 1}

N 行出力してください。i + 1 行目 (0 ≤ i ≤ N-1) には、組織 i についての答え \text{ans}_i を出力してください。

サンプルプログラム
# x 番の組織が親組織に提出する報告書の枚数を返す関数
def num_report(children, x):
    # ここに追記して再帰関数を実装する

# これ以降の行は変更しなくてよい
N = int(input())
# p[i] : 組織 i の親組織
# 組織 0 の親組織は存在しないので -1 を入れておく
# 組織 0 に相当する部分は入力で与えられないため、リスト [-1] を作成して "+" 演算子で結合する
p = [-1] + [int(c) for c in input().split()] 

# children[i] = 組織 i の子組織のリスト
children = [[] for _ in range(N)]
for i in range(1, N):
    parent = p[i] # 組織 i の親組織は parent
    children[parent].append(i) # parent の子組織リストに i を追加

# 各組織について答えを計算し出力する
for i in range(N):
    res = num_report(children, i)
    print(res)

関数 num_report の引数 children は二次元リストで、組織 x の子組織の番号一覧はchildren[x] で得ることができます。

ジャッジでは以下の入力例以外のケースに関してもテストされることに注意。

入力例1

6
0 0 1 1 4

出力例1

6
4
1
1
2
1

組織の関係は次の図のようになります。（子組織から親組織の向きに矢印が向いています。）

番号の隣に書いてある青い数字が各組織についての答えです。

入力例2

8
0 0 1 2 0 3 6

出力例2

8
4
2
3
1
1
2
1

組織の関係は次の図のようになります。（子組織から親組織の向きに矢印が向いています。）

番号の隣に書いてある青い数字が各組織についての答えです。

ヒント

クリックでヒントを開く
  • 「組織 x が親組織へ提出する枚数」= 1 + 組織 x の全ての子組織 c についての「c から受け取った報告書の枚数」の合計
  • 「c から受け取った報告書の枚数」=「c が親組織に提出する枚数」
  • 子組織が無いような組織について、その組織が親組織に提出する報告書の枚数は 1 枚

次のようにすることで x 番の組織の子組織についての処理が行えます。

for c in children[x]:
    # (c についての処理)

この問題は 2.05.再帰関数 の例題に非常に近い問題となっているので、そちらも参考にしてください。

テスト入出力

書いたプログラムがACにならず、原因がどうしてもわからないときだけ見てください。

クリックでテスト入出力を見る

テスト入力1

20
0 1 1 3 0 0 1 3 5 9 6 8 8 8 0 4 7 12 13

テスト出力1

20
13
1
9
2
3
2
2
6
2
1
1
2
2
1
1
1
1
1
1

テスト入力2

30
0 1 0 1 0 3 1 2 8 6 1 3 0 4 2 3 0 14 16 13 5 2 16 14 19 2 7 2 26

テスト出力2

30
16
8
8
4
2
2
2
2
1
1
1
1
2
3
1
4
1
1
2
1
1
1
1
1
1
2
1
1
1

テスト入力3

50
0 0 0 2 3 1 6 3 4 0 9 5 2 12 7 13 14 1 3 14 2 10 17 7 8 1 15 11 19 29 26 20 7 18 10 24 19 2 19 29 29 9 21 42 0 19 24 44 26

テスト出力3

50
14
13
18
7
7
8
7
2
6
3
2
6
2
5
2
1
2
2
8
2
2
1
1
3
1
3
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
3
1
2
1
1
1
1
1

解答例

必ず自分で問題に挑戦してみてから見てください。

クリックで解答例を見る 
# x 番の組織が親組織に提出する報告書の枚数を返す関数
def num_report(children, x):
    # ここに追記して再帰関数を実装する
    # ベースケース
    if not children[x]:
        return 1
    # 再帰ステップ
    ans = 1 # 自身の報告書
    for c in children[x]:
        ans += num_report(children, c)
    return ans

# これ以降の行は変更しなくてよい
N = int(input())
# p[i] : 組織 i の親組織
# 組織 0 の親組織は存在しないので -1 を入れておく
# 組織 0 に相当する部分は入力で与えられないため、リスト [-1] を作成して "+" 演算子で結合する
p = [-1] + list(map(int, input().split())) 

# children[i] = 組織 i の子組織のリスト
children = [[] for _ in range(N)]
for i in range(1, N):
    parent = p[i] # 組織 i の親組織は parent
    children[parent].append(i) # parent の子組織リストに i を追加

# 各組織について答えを計算し出力する
for i in range(N):
    res = num_report(children, i)
    print(res)