ABC026 C 高橋君の給料
考えた解法を言語化した。
解説に書いてある解法、再帰で解いた。 ただ、なんとなく通してしまったのであまり考えていない。 そこで、ちょっとは頭を使ってみる。
#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。なので、それだけを分岐させる。
社員番号が高い社員から順番に給料がわかる。
今回はすんなり解けた感じがあるけれど、そのすんなりは偶然だったような。