AtCoder Beginner Contest 026 C – 高橋君の給料をPython3で解く

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典：
AtCoder Beginner Contest 026 C – 高橋君の給料

木の頂点をたどりながら、数値を計算していく問題。
下から順番に給料を決めていってもいいが、再帰関数を用いる方が簡単に書けるだろう。今回は構造が木＆求めるのが高橋君の給料のみのため、特にメモ化なども行っていない。

# AtCoder Beginner Contest 026 C - 高橋君の給料
# https://atcoder.jp/contests/abc026/tasks/abc026_c
# tag: グラフ 木 再帰関数 高橋君

# 解き方はいろいろあると思うが、ここでは再帰関数を用いて解いている。
# 人数も少ないので、割と適当に書いてもどうにかなるだろう。

def main():
    N = int(input())
    path_dat = [int(input()) for _ in range(N-1)]

    # 1-indexed のままグラフを構成（どっちでもいいけど……）
    # グラフ～と聞くとややこしそうだが、各従業員ごとに
    # 直属の部下をリストにしているだけ（隣接リスト）。
    paths = [[] for _ in range(N+1)]
    for i, boss in enumerate(path_dat, start=2):
        paths[boss].append(i)

    # 再帰関数
    def get_payment(idx):
        # 部下がいないなら、給料は 1
        if paths[idx] == []:
            return 1

        # 部下がいるときは、部下の給料を取得してそこから計算
        staff_payments = [get_payment(p) for p in paths[idx]]
        return min(staff_payments) + max(staff_payments) + 1

    # 高橋君の給料を求める
    print(get_payment(1))

main()

abc026_c.py view raw

関連

コメントを残すコメントをキャンセル