AtCoder Beginner Contest 026 C - 今日から始める競技プロ日記
はじめに
chokudaiさんが今日の一問としてツイートしていたABC026のC問題を解いてみた。
14分で解いた。目標は20分だったのでまずまず良さげ。
今日の一問！ABC026より、高橋君の給料。今だと300点くらい？
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2019年8月20日
これも昨日と同じく「実装出来てほしい」系の問題。緑の人の目標タイムが20分くらい、って感じ。https://t.co/Z2MuWxj8lp
高橋君の給料
社員がN人、社長の社員番号が1である。
社員番号2～Nの社員には必ず直属の上司が一人存在する。
直属の部下がいない社員の給料は1。
直属の部下がいる社員の給料は、max(直属の部下たちの給料) + min(直属の部下たちの給料) + 1。
社長の給料を求めよ。
解き方
末端の社員から給料を求めていけば、 最終的に社長の給料が求められるなーと考えた（当たり前だけど）。
そこで問題なのがどうやってデータを扱うか。
必要な情報はある社員にどんな部下がいるかということ。
ということでこんな感じにまとめてみる。
サンプル2の場合
社員数：7人
| 社員番号 | 直属の上司 |
|---|---|
| 1 | なし |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 2 |
| 6 | 3 |
| 7 | 3 |
各社員の直属の部下たちをまとめる。
| 社員番号 | 直属の部下たち |
|---|---|
| 1 | 2, 3 |
| 2 | 4, 5 |
| 3 | 6, 7 |
| 4 | なし |
| 5 | なし |
| 6 | なし |
| 7 | なし |
このようにまとめた後、社員番号が一番大きい社員の給料から求めていく。
社員番号7,6,5,4の社員は部下がいないので給料1。
社員番号3の社員の部下は6,7で、max=1, min=1だから、社員番号3の社員の給料は1+1+1=3。
同じように計算して社員番号2の給料は1+1+1=3。
そして最後に社長（社員番号1）の給料は3+3+1=7。
したがって出力すべき答えは7。
コード
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int N;
cin >> N;
vector<vector<int>> v(N+1);
vector<int> c(N+1, 1);
for(int i = 1; i < N; i++)
{
int a;
cin >> a;
v[a-1].push_back(i);
}
for(int i = N-1; i >= 0; i--)
{
if(v[i].size() == 0) continue;
int maxv = 1;
int minv = 1<<29;
for(auto& t: v[i])
{
maxv = max(maxv, c[t]);
minv = min(minv, c[t]);
}
c[i] = maxv + minv + 1;
}
cout << c[0] << endl;
return 0;
}
おわりに
良問だった
