C - 高橋君の給料

時間制限 : 2sec / メモリ制限 : 256MB

問題文

高橋君は、社員が N 人いる会社の社長です。高橋君の会社では、以下のように給料が決まっています。

高橋君を含む社員の全員が、 1 から N までの社員番号を持っている。高橋君の社員番号はもちろん 1 である。高橋君以外の社員には、必ず自分より社員番号が小さい上司がただ一人存在する。自分が上司になっている社員のことを、直属の部下と呼ぶ。直属の部下がいない社員の給料は 1 であり、直属の部下がいる社員の給料は、max(その社員の直属の部下の給料)+min(その社員の直属の部下の給料)+1 である。直属の部下が一人しかいない場合は、その部下の給料の 2 倍 + 1 が、その社員の給料となる。この時、高橋君の給料を求めなさい。

note

深さ優先で再帰させてやればよい

#include <iostream>
#include <vector>
#define ll long long
#define NMAX 21
using namespace std;

const ll INF = 1LL<<60;

struct Worker{
    ll salary;
    int manager;
};

class MrTakahashiSalary
{
public:
    int n;
    vector<Worker> workers;
    vector<int> graph[NMAX]; 

    MrTakahashiSalary();
    ~MrTakahashiSalary();
    void exec();
    ll dfs(int index);

};

MrTakahashiSalary::MrTakahashiSalary(){
    cin >> n;
    Worker takahashi = {-1, -1};
    workers.push_back(takahashi);
    for (int i = 1; i < n; ++i)
    {
        Worker w;
        cin >> w.manager;
        w.manager--;
        w.salary = -1;
        graph[w.manager].push_back(i);
        workers.push_back(w);
    }
}

MrTakahashiSalary::~MrTakahashiSalary(){}

void MrTakahashiSalary::exec(){
    cout << dfs(0) << endl;
}

ll MrTakahashiSalary::dfs(int index){
    if(workers[index].salary != -1) return workers[index].salary;
    if(graph[index].size() == 0) return 1;
    ll min_salary = INF;
    ll max_salary = 0;
    for (int i = 0; i < graph[index].size(); ++i)
    {
        min_salary = min(dfs(graph[index][i]), min_salary);
        max_salary = max(dfs(graph[index][i]), max_salary);
    }
    workers[index].salary = min_salary + max_salary + 1;
    return workers[index].salary;
}

int main(){
    MrTakahashiSalary mts = MrTakahashiSalary();
    mts.exec();
}

D - 高橋君ボール1号

時間制限 : 2sec / メモリ制限 : 256MB

問題文

高橋君は野球が得意です。高橋君は、高橋君ボール 1 号という変化球を投げることが出来ます。

このボールは、投げてから t 秒後のボールの位置を f(t) とすると、 f(t)=A×t+B×sin(C×t×π) と表すことが出来ます。

あなたは、t≧0 かつ f(t)=100 となるタイミングで、ボールを打たなければいけません。この時の t を求めたいです。

note

中間値の定理が使えるので、二分探索が出来る

#include <iostream>
#include <algorithm>
#include <cmath>
#include <math.h>
#define eps 10e-7

using namespace std;

class MrTakahashiBall
{
public:
    double a, b, c;
    MrTakahashiBall();
    ~MrTakahashiBall();
    double computeF(double t);
    void exec();
};

MrTakahashiBall::MrTakahashiBall(){
    cin >> a >> b >> c;
}

MrTakahashiBall::~MrTakahashiBall(){}

double MrTakahashiBall::computeF(double t){
    return a * t + b * sin(c * t * M_PI);
}

void MrTakahashiBall::exec(){
    double r, l, mid, f_value;
    l = 0;
    r = 20000;
    while(true){
        mid = (r + l)/ 2.0;
        f_value = computeF(mid);
        if(fabs(f_value - 100) < eps) break;
        if(f_value > 100){
            r = mid;
        }else{
            l = mid;
        }
    }
    printf("%.12lf\n", mid );
}

int main(){
    MrTakahashiBall mrb = MrTakahashiBall();
    mrb.exec();
}

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 026 #39

C - 高橋君の給料

問題文

note

D - 高橋君ボール1号

問題文

note