🐥

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

2025/01/01に公開

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

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

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

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

 アプローチ会社の組織構造を木構造として捉え、深さ優先探索（DFS）を用いて給料を計算する。

 解法手順会社の組織構造を表現するデータ構造を作成する。
各社員の直属の部下を格納するリストを用意する。
入力から組織構造を構築する。
各社員の上司情報を読み取り、上司の部下リストに追加する。
深さ優先探索（DFS）を実装する関数を定義する。
この関数は、与えられた社員の給料を計算して返す。
DFS関数内で以下の処理を行う：
部下がいない場合、給料は1を返す。
部下がいる場合、各部下の給料を再帰的に計算する。
部下の給料のリストから、最大値と最小値を求める。
給料を計算式（max + min + 1）に従って計算し、返す。
社長（社員番号1、インデックス0）からDFSを開始する。
計算結果（社長の給料）を出力する。

 ACコードac.py
import sys
sys.setrecursionlimit(1000000)  # 再帰の深さ制限を増やす

def io_func():
    # 社員数Nを入力として受け取る
    N = int(input())
    
    # 各社員の部下リストを初期化
    subordinates = [[] for _ in range(N)]
    
    # 2番目の社員から順に上司の情報を入力として受け取り、組織構造を構築
    for i in range(1, N):
        boss = int(input())
        subordinates[boss - 1].append(i)
    
    return N, subordinates

def solve(N, subordinates):
    def dfs(employee):
        # 部下がいない場合、給料は1
        if len(subordinates[employee]) == 0:
            return 1
        
        # 部下がいる場合、各部下の給料を再帰的に計算
        salaries = [dfs(sub) for sub in subordinates[employee]]
        
        # 部下の給料の最大値と最小値を求め、自身の給料を計算
        return max(salaries) + min(salaries) + 1
    
    # 社長（インデックス0）から探索を開始し、結果を返す
    return dfs(0)

if __name__== "__main__":
    # メイン処理
    N, subordinates = io_func()
    result = solve(N, subordinates)
    print(result)

###
# - N: 社員の総数
# - subordinates: 各社員の直属の部下を格納するリスト
# - employee: DFS関数内で現在処理している社員のインデックス
# - salaries: 部下の給料のリスト

# 1. 再帰の深さ制限を増やす。
# 2. io_func関数:
#    - 社員数Nを入力として受け取る。
#    - 各社員の部下リストを初期化する。
#    - 2番目の社員から順に上司の情報を入力として受け取り、組織構造を構築する。
#    - NとsubordinatesリストをsolveA関数に渡す。
# 3. solve関数:
#    - 内部にdfs関数を定義する。
#    - dfs関数は以下の処理を行う：
#      a. 部下がいない場合、給料1を返す。
#      b. 部下がいる場合、各部下の給料を再帰的に計算する。
#      c. 部下の給料の最大値と最小値を求め、自身の給料を計算して返す。
#    - 社長（インデックス0）からdfs探索を開始し、結果を返す。
# 4. メイン処理:
#    - io_func関数を呼び出してNとsubordinatesを取得する。
#    - solve関数を呼び出して結果を得る。
#    - 結果（社長の給料）を出力する。

 メモ再帰

給料の計算が部下の給料に依存しているため、再帰的な思考が必要。

最下層の社員から順に計算を積み上げていく発想が求められます。
深さ優先探索（DFS）の理解

組織構造を効率的に探索するために、DFSアルゴリズムの理解と実装能力が必要。

問題

要約

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

アプローチ

解法手順

ACコード

メモ

Discussion