読者です 読者をやめる 読者になる 読者になる

noyのブログ

プログラミングとかゲームとか

ABC026 C 高橋君の給料

競技プログラミング

C: 高橋君の給料 - AtCoder Beginner Contest 026 | AtCoder


解説に書いてある解法、再帰で解いた。
ただ、なんとなく通してしまったのであまり考えていない。
そこで、ちょっとは頭を使ってみる。

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define itrep(it, a) for(it = (a).begin(); it != (a).end(); it++)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (1 << 30)
using namespace std;
 
int n, inp[30];
 
int solve(int d){
    int high = 0, low = INF;
    rep(i,n){
        if(inp[i] == d){
            int down = solve(i + 1);
            high = max(down, high);
            low = min(down, low);
        }
    }
    if(high == 0 && low == INF) return 1;
    else return high + low + 1;
}
 
int main(){
    cin >> n;
    for(int i = 1; i < n; i++){
        cin >> inp[i];
    }
    cout << solve(1) << endl;
}

solve関数で、社員番号dの給料を計算している。

社員番号dの給料は、部下の給料から求められる。inp[i] == d のとき、社員番号iはdの部下である。
社員番号iの給料も上記と同じように求められるので、再帰を使うことができる。
再帰で求めたい社員の部下の給料を求めていく。部下がいない社員は給料が1。なので、それだけを分岐させる。

社員番号が高い社員から順番に給料がわかる。


今回はすんなり解けた感じがあるけれど、そのすんなりは偶然だったような。