{ }codelper
再帰整数の割り算P0265

先に亡くなった子の取り分は孫へ

1 番の人が亡くなって M ウォンを残し、このお金を家系の木に沿って分ける。
人は 1 番から n 番までいて、1 番を除くすべての人はちょうど一人の人の子である。
全員が 1 番の子孫である。
人ごとに生きている（alive）か、すでに亡くなっている（dead）かが決まっていて、1 番は亡くなっている。
まず相続人になれる人を決める。
生きている人は相続人になれる。
亡くなった人は、相続人になれる子が一人でもいるときだけ相続人になれる。
ある人 p にお金 X ウォンが来たら、p の子のうち相続人になれる人たちだけに分ける。
そういう子が c 人なら、一人ずつ X を c で割った商だけ受け取り、余り r ウォンはその c 人のうち長子から r 人が 1 ウォンずつ多く受け取る。
取り分を受け取った子が生きていれば、そのお金を持つ。
亡くなった子なら、その取り分は同じ規則でその子の子たちに下りていく。
1 番の M ウォンでこれを始める。
1 番の子のうち相続人になれる人がいなければ、M ウォンはすべて国庫に入る。
一行目に n と M、続く n 行に 1 番から n 番の人が順に「状態 k 子1 … 子k」で与えられる。
値は空白一つで区切られる。
状態は alive か dead で、子は長子から年の順に書かれている（番号の順とは違うことがある）。
一行目に 1 番から n 番まで人ごとに受け取って持っているお金を空白一つずつ区切って出力せよ。
亡くなった人とお金を受け取れなかった人は 0 である。
二行目に国庫に入ったお金を出力せよ。
国庫に入ったお金がなければ 0 である。
金額はカンマなしの数字だけで書く。
相続人かどうかを決めることと、お金を下ろしていくことを、それぞれ再帰関数にしてみよう。

入力
1 ≤ n ≤ 1,000、0 ≤ M ≤ 1,000,000,000,000（整数）。
k は 0 以上で、1 番を除くすべての人がだれかの子としてちょうど一回現れ、1 番はだれの子としても現れない。
1 番の状態は dead である。
1 番から最も遠い人までの世代数は 1,000 以下（一列につながった家系もある）
出力
二行
例 1 · stdin
7 101
dead 3 2 3 4
alive 0
dead 2 5 6
dead 1 7
alive 0
alive 0
dead 0
stdout
0 51 0 0 25 25 0
0
例 2 · stdin
3 7
dead 2 2 3
dead 0
dead 0
stdout
0 0 0
7
main.py
入力(stdin)

実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。

$ 準備完了

コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。

ほかの言語では？言語別の解答を見る · 8 言語の解答

家系の木の枝ごとに同じ規則が繰り返されるので、「この人の下を決める」再帰関数二つで解けます。
一つは下から相続人かどうかを決め（子を先に決めてから自分を決めます）、もう一つは上から取り分を下ろしていきます。
二つの関数が一緒に使う表（生きているか、子の一覧、受け取ったお金）は、Python・JS・TS は外側の変数、Java・C#・C は静的変数・グローバル配列、C++ はグローバルな vector、Craykon はプログラムのいちばん外側で作った名前に置きます。
落とし穴は五つ：① 亡くなった人は「子がいる」ではなく「相続人になれる子がいる」ときだけ相続人です。
子も孫もみな先に亡くなっていれば相続人ではなく、取り分を受け取りません。
だから相続人かどうかを決めることも再帰です。
② 相続人を決めるとき、Python の any()、JS・TS の some()、C・C++・Java・C# の || は最初の真で止まるので、後ろの子たちを決めずに通り過ぎます。
すべての子を先に決めておいてから結果をまとめます。
③ 割る数は相続人になれる子の数です。
子全体で割ると、相続人でない子の取り分が消えます。
余りは長子から 1 ウォンずつです。
④ 一列につながった家系では再帰が 1,000 段まで入ります。
Python は既定の再帰の上限が 1,000 なので sys.setrecursionlimit で増やす必要があります。
他の言語はこの深さなら大丈夫で、Craykon も約 3,000 段まで呼べます。
⑤ M は 10^12 までなので、C・C++・Java・C# では long long・long で受けます。
int は約 21 億までです。
Python の int は限りがなく、JS・TS・Craykon の数は 2^53 まで正確なので大丈夫です。
商と余りは Python divmod、JS・TS Math.floor(x / c) と %、Craykon 数学.商(x, c)（韓国語で 수학.몫(x, c)）と %、残りの言語は整数の / と % です（お金は 0 以上なので切り捨ての向きは関係ありません）。

Pythonmain.py · 49 行
import sys sys.setrecursionlimit(10000)  # 세대가 1,000까지 이어진다. 기본 한도(1,000)로는 모자란다 lines = sys.stdin.read().split("\n")n, money = map(int, lines[0].split())alive = [False] * (n + 1)children = [[] for _ in range(n + 1)]for i in range(1, n + 1):    p = lines[i].split()    alive[i] = p[0] == "alive"    children[i] = [int(c) for c in p[2:]] heir = [False] * (n + 1)  def mark(p):    """p가 상속인이 될 수 있는지 정한다. 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다."""    found = False    for c in children[p]:        if mark(c):  # 자식을 모두 정해 두어야 하므로 any()로 일찍 멈추지 않는다            found = True    heir[p] = alive[p] or found    return heir[p]  got = [0] * (n + 1)  def share(p, amount):    """p에게 온 amount를 p의 상속인 자식들에게 나눈다."""    heirs = [c for c in children[p] if heir[c]]    each, rest = divmod(amount, len(heirs))    for i, c in enumerate(heirs):        part = each + (1 if i < rest else 0)  # 나머지는 맏이부터 1원씩        if alive[c]:            got[c] += part        else:            share(c, part)  # 먼저 떠난 자식의 몫은 그 자식들에게 내려간다  mark(1)treasury = 0if any(heir[c] for c in children[1]):    share(1, money)else:    treasury = moneyprint(" ".join(map(str, got[1:])))print(treasury)
JavaScriptmain.js · 38 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, money] = lines[0].trim().split(" ").map(Number); // 10^12도 number(2^53까지 정확)로 충분하다const alive = [false];const children = [[]];for (let i = 1; i <= n; i++) {  const p = lines[i].trim().split(" ");  alive.push(p[0] === "alive");  children.push(p.slice(2).map(Number));} const heir = new Array(n + 1).fill(false);// p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다function mark(p) {  let found = false;  for (const c of children[p]) if (mark(c)) found = true; // some()은 일찍 멈춰서 뒤의 자식을 정하지 못한다  heir[p] = alive[p] || found;  return heir[p];} const got = new Array(n + 1).fill(0);// p에게 온 amount를 p의 상속인 자식들에게 나눈다function share(p, amount) {  const heirs = children[p].filter((c) => heir[c]);  const each = Math.floor(amount / heirs.length);  const rest = amount % heirs.length;  heirs.forEach((c, i) => {    const part = each + (i < rest ? 1 : 0); // 나머지는 맏이부터 1원씩    if (alive[c]) got[c] += part;    else share(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다  });} mark(1);let treasury = 0;if (children[1].some((c) => heir[c])) share(1, money);else treasury = money;console.log(got.slice(1).join(" "));console.log(String(treasury));
TypeScriptmain.ts · 40 行
import { readFileSync } from "node:fs"; const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, money] = lines[0].trim().split(" ").map(Number); // 10^12도 number(2^53까지 정확)로 충분하다const alive: boolean[] = [false];const children: number[][] = [[]];for (let i = 1; i <= n; i++) {  const p = lines[i].trim().split(" ");  alive.push(p[0] === "alive");  children.push(p.slice(2).map(Number));} const heir: boolean[] = new Array<boolean>(n + 1).fill(false);// p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다function mark(p: number): boolean {  let found = false;  for (const c of children[p]) if (mark(c)) found = true;  heir[p] = alive[p] || found;  return heir[p];} const got: number[] = new Array<number>(n + 1).fill(0);// p에게 온 amount를 p의 상속인 자식들에게 나눈다function share(p: number, amount: number): void {  const heirs = children[p].filter((c) => heir[c]);  const each = Math.floor(amount / heirs.length);  const rest = amount % heirs.length;  heirs.forEach((c, i) => {    const part = each + (i < rest ? 1 : 0); // 나머지는 맏이부터 1원씩    if (alive[c]) got[c] += part;    else share(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다  });} mark(1);let treasury = 0;if (children[1].some((c) => heir[c])) share(1, money);else treasury = money;console.log(got.slice(1).join(" "));console.log(String(treasury));
JavaMain.java · 59 行
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List; public class Main {    static boolean[] alive, heir;    static int[][] children;    static long[] got;     // p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다    static boolean mark(int p) {        boolean found = false;        for (int c : children[p]) if (mark(c)) found = true;        heir[p] = alive[p] || found;        return heir[p];    }     // p에게 온 amount를 p의 상속인 자식들에게 나눈다    static void share(int p, long amount) {        List<Integer> heirs = new ArrayList<>();        for (int c : children[p]) if (heir[c]) heirs.add(c);        long each = amount / heirs.size(), rest = amount % heirs.size();        for (int i = 0; i < heirs.size(); i++) {            int c = heirs.get(i);            long part = each + (i < rest ? 1 : 0); // 나머지는 맏이부터 1원씩            if (alive[c]) got[c] += part;            else share(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다        }    }     public static void main(String[] args) throws Exception {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        String[] first = in.readLine().trim().split(" ");        int n = Integer.parseInt(first[0]);        long money = Long.parseLong(first[1]); // 10^12는 int를 넘는다        alive = new boolean[n + 1];        heir = new boolean[n + 1];        children = new int[n + 1][];        got = new long[n + 1];        for (int i = 1; i <= n; i++) {            String[] p = in.readLine().trim().split(" ");            alive[i] = p[0].equals("alive");            int k = Integer.parseInt(p[1]);            children[i] = new int[k];            for (int j = 0; j < k; j++) children[i][j] = Integer.parseInt(p[2 + j]);        }        mark(1);        boolean anyHeir = false;        for (int c : children[1]) if (heir[c]) anyHeir = true;        long treasury = 0;        if (anyHeir) share(1, money);        else treasury = money;        StringBuilder out = new StringBuilder();        for (int i = 1; i <= n; i++) out.append(i > 1 ? " " : "").append(got[i]);        out.append('\n').append(treasury).append('\n');        System.out.print(out);    }}
C#Main.cs · 57 行
using System;using System.Collections.Generic;using System.Linq; class Program{    static bool[] alive = Array.Empty<bool>(), heir = Array.Empty<bool>();    static int[][] children = Array.Empty<int[]>();    static long[] got = Array.Empty<long>();     // p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다    static bool Mark(int p)    {        bool found = false;        foreach (int c in children[p]) if (Mark(c)) found = true;        heir[p] = alive[p] || found;        return heir[p];    }     // p에게 온 amount를 p의 상속인 자식들에게 나눈다    static void Share(int p, long amount)    {        List<int> heirs = children[p].Where(c => heir[c]).ToList();        long each = amount / heirs.Count, rest = amount % heirs.Count;        for (int i = 0; i < heirs.Count; i++)        {            int c = heirs[i];            long part = each + (i < rest ? 1 : 0); // 나머지는 맏이부터 1원씩            if (alive[c]) got[c] += part;            else Share(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다        }    }     static void Main()    {        string[] first = Console.ReadLine()!.Trim().Split(' ');        int n = int.Parse(first[0]);        long money = long.Parse(first[1]); // 10^12는 int를 넘는다        alive = new bool[n + 1];        heir = new bool[n + 1];        children = new int[n + 1][];        children[0] = Array.Empty<int>();        got = new long[n + 1];        for (int i = 1; i <= n; i++)        {            string[] p = Console.ReadLine()!.Trim().Split(' ');            alive[i] = p[0] == "alive";            children[i] = p.Skip(2).Select(int.Parse).ToArray();        }        Mark(1);        long treasury = 0;        if (children[1].Any(c => heir[c])) Share(1, money);        else treasury = money;        Console.WriteLine(string.Join(" ", got.Skip(1)));        Console.WriteLine(treasury);    }}
C++main.cpp · 59 行
#include <iostream>#include <string>#include <vector> int n;std::vector<bool> alive, heir;std::vector<std::vector<int>> children;std::vector<long long> got; // 10^12는 int를 넘는다 // p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다bool mark(int p) {    bool found = false;    for (int c : children[p])        if (mark(c)) found = true; // ||로 이으면 짧은 계산 때문에 뒤의 자식을 정하지 못한다    heir[p] = alive[p] || found;    return heir[p];} // p에게 온 amount를 p의 상속인 자식들에게 나눈다void share(int p, long long amount) {    std::vector<int> heirs;    for (int c : children[p])        if (heir[c]) heirs.push_back(c);    long long count = static_cast<long long>(heirs.size());    long long each = amount / count, rest = amount % count;    for (long long i = 0; i < count; i++) {        int c = heirs[i];        long long part = each + (i < rest ? 1 : 0); // 나머지는 맏이부터 1원씩        if (alive[c]) got[c] += part;        else share(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다    }} int main() {    std::ios::sync_with_stdio(false);    long long money;    std::cin >> n >> money;    alive.assign(n + 1, false);    heir.assign(n + 1, false);    children.assign(n + 1, {});    got.assign(n + 1, 0);    for (int i = 1; i <= n; i++) {        std::string st;        int k;        std::cin >> st >> k;        alive[i] = st == "alive";        children[i].resize(k);        for (int& c : children[i]) std::cin >> c;    }    mark(1);    bool anyHeir = false;    for (int c : children[1])        if (heir[c]) anyHeir = true;    long long treasury = 0;    if (anyHeir) share(1, money);    else treasury = money;    for (int i = 1; i <= n; i++) std::cout << (i > 1 ? " " : "") << got[i];    std::cout << '\n' << treasury << '\n';}
Cmain.c · 58 行
#include <stdio.h>#include <string.h> #define MAXN 1001 static int alive[MAXN], heir[MAXN];static int kidStart[MAXN], kidCount[MAXN], kids[MAXN]; /* p의 자식은 kids[kidStart[p]]부터 kidCount[p]개 */static long long got[MAXN]; /* 10^12는 int를 넘는다 */ /* p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다 */static int mark(int p) {    int found = 0;    for (int j = 0; j < kidCount[p]; j++)        if (mark(kids[kidStart[p] + j])) found = 1;    heir[p] = alive[p] || found;    return heir[p];} /* p에게 온 amount를 p의 상속인 자식들에게 나눈다 */static void share(int p, long long amount) {    int count = 0;    for (int j = 0; j < kidCount[p]; j++)        if (heir[kids[kidStart[p] + j]]) count++;    long long each = amount / count, rest = amount % count;    int i = 0;    for (int j = 0; j < kidCount[p]; j++) {        int c = kids[kidStart[p] + j];        if (!heir[c]) continue;        long long part = each + (i < rest ? 1 : 0); /* 나머지는 맏이부터 1원씩 */        i++;        if (alive[c]) got[c] += part;        else share(c, part); /* 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 */    }} int main(void) {    int n;    long long money;    scanf("%d %lld", &n, &money);    int used = 0;    for (int i = 1; i <= n; i++) {        char st[8];        scanf("%7s %d", st, &kidCount[i]);        alive[i] = strcmp(st, "alive") == 0;        kidStart[i] = used;        for (int j = 0; j < kidCount[i]; j++) scanf("%d", &kids[used++]);    }    mark(1);    int anyHeir = 0;    for (int j = 0; j < kidCount[1]; j++)        if (heir[kids[kidStart[1] + j]]) anyHeir = 1;    long long treasury = 0;    if (anyHeir) share(1, money);    else treasury = money;    for (int i = 1; i <= n; i++) printf(i > 1 ? " %lld" : "%lld", got[i]);    printf("\n%lld\n", treasury);    return 0;}
Craykonmain.cray · 89 行
// 함수 안에서 쓰는 이름(p, c, found, amount, 상속자식, 몫, 나머지, part, j)은 아래 본문에서 쓰지 않는다:// 본문 맨 바깥에서 만든 이름(살아있음, 자식, 상속인, 받은돈)은 모든 호출이 함께 쓰는 하나가 된다 // p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다정하기(p){    found = 偽;    それぞれ (c の中 자식[p])    {        もし (정하기(c))        {            found = 真;        }    }    상속인[p] = 살아있음[p] || found;    返す 상속인[p];} // p에게 온 amount를 p의 상속인 자식들에게 나눈다나누어주기(p, amount){    상속자식 = [];    それぞれ (c の中 자식[p])    {        もし (상속인[c])        {            상속자식.追加(c);        }    }    몫 = 数学.商(amount, 상속자식.個数);    나머지 = amount % 상속자식.個数;    繰り返す (j = 0; j < 상속자식.個数; j++)    {        c = 상속자식[j];        part = 몫;        もし (j < 나머지)        {            part = 몫 + 1;        }        もし (살아있음[c])        {            받은돈[c] += part;        }        でなければ        {            나누어주기(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다        }    }} 첫줄 = コンソール.行読み().空白除去().分ける(" ");n = 첫줄[0].数に();돈 = 첫줄[1].数に(); // 10^12도 2^53 안이라 정확하다살아있음 = 新リスト(n + 1, 偽);자식 = [[]];상속인 = 新リスト(n + 1, 偽);받은돈 = 新リスト(n + 1, 0);繰り返す (i = 1; i <= n; i++){    칸 = コンソール.行読み().空白除去().分ける(" ");    살아있음[i] = 칸[0] == "alive";    목록 = [];    繰り返す (k = 2; k < 칸.個数; k++)    {        목록.追加(칸[k].数に());    }    자식.追加(목록);}정하기(1);상속인있음 = 偽;それぞれ (x の中 자식[1]){    もし (상속인[x])    {        상속인있음 = 真;    }}국고 = 0;もし (상속인있음){    나누어주기(1, 돈);}でなければ{    국고 = 돈;}받은돈.位置で取り除く(0);コンソール.書く(받은돈.つなぐ(" "));コンソール.書く(국고);