🔥

【競技プログラミング】AtCoder Beginner Contest 026_C問題

2025/01/02に公開

 問題https://atcoder.jp/contests/abc026/tasks/abc026_c

 要約社員番号は1からNまであり、高橋君の社員番号は1。
高橋君以外の社員には、必ず1人の上司がいます（社員番号が自分より小さい）。
給料の決め方
直属の部下がいない社員の給料は1。
直属の部下がいる社員の給料は、以下の計算式で決まる

max(直属の部下の給料) + min(直属の部下の給料) + 1
直属の部下が1人しかいない場合は、その部下の給料の2倍 + 1となる。
高橋君（社長）の給料を求める。
N: 会社の社員数

 既存投稿一覧ページへのリンク一覧ページ

前回の挑戦

 解法手順社員数Nを入力として受け取る。
会社の組織構造を表現するためのリスト（隣接リスト）Gを作成する。
N-1回のループで各社員の上司の情報を入力として受け取り、Gに追加する。
深さ優先探索（DFS）を行う関数dfsを定義する。
この関数は社員番号xを引数として受け取る。
部下がいない場合（葉ノード）は、給料1を返す。
部下がいる場合は、各部下の給料をDFSで計算し、リストに格納する。
部下の給料リストから最大値と最小値を取得し、計算式に従って給料を返す。
dfs関数を社長（社員番号1）に対して呼び出し、結果を出力する。

 ACコードac.py
def io_func():
    # 社員数Nを入力として受け取る
    n = int(input())
    
    # 会社の組織構造を表現するためのリスト（隣接リスト）Gを作成する
    G = [[] for _ in range(n + 1)]
    
    # N-1回のループで各社員の上司の情報を入力として受け取り、Gに追加する
    for i in range(n-1):
        b = int(input())
        G[b].append(i+2)
    
    return n, G

def dfs(x, G):
    # 部下がいない場合（葉ノード）は、給料1を返す
    if len(G[x]) == 0:
        return 1
    else:
        # 部下がいる場合は、各部下の給料をDFSで計算し、リストに格納する
        subordinate_salaries = []
        for subordinate in G[x]:
            subordinate_salaries.append(dfs(subordinate, G))
        
        # 部下の給料リストから最大値と最小値を取得し、計算式に従って給料を返す
        return max(subordinate_salaries) + min(subordinate_salaries) + 1

def solve():
    # 入力を受け取る
    n, G = io_func()
    
    # dfs関数を社長（社員番号1）に対して呼び出し、結果を出力する
    result = dfs(1, G)
    print(result)

if __name__=="__main__":
    # メイン処理
    solve()

###
# n: 社員数
# G: 会社の組織構造を表す隣接リスト
# x: 現在の社員番号
# subordinate_salaries: 部下の給料のリスト

# 1. io_func関数:
#    - 入力を受け取り、社員数nと組織構造Gを返す
# 2. dfs関数:
#    - 深さ優先探索を行い、各社員の給料を計算する
#    - 部下がいない場合は1を返す
#    - 部下がいる場合は、部下の給料の最大値と最小値を使って計算する
# 3. solve関数:
#    - io_func関数を呼び出して入力を受け取る
#    - dfs関数を呼び出して社長（社員番号1）の給料を計算し、結果を出力する
# 4. メイン処理:
#    - solve関数を呼び出して問題を解く

問題

要約

既存投稿一覧ページへのリンク

解法手順

ACコード

Discussion