백준 16631번 Longest Life

문제 요약

문제가 좀 복잡한 듯 하다. 알약이 p개 주어진다. 각 알약은 x-y 형태로 표현할 수 있는데 해당 알약을 먹으면 실제 시간이 x초 지날 동안 신체 나이는 x초 지나간다.

그리고 알약을 먹지 않는 상태에서 알약을 먹기 시작하거나 먹는 알약을 갈아탈 때마다 c초 만큼 신체 시간을 소모한다.

각 알약은 사용가능해지는 시기 $t_i$를 가진다.

아무 알약도 먹지 않았을 때 살 수 있는 신체 나이 n이 주어지면 각 알약을 적절히 먹었을 때 살 수 있는 최장 시간을 구해야 한다.

풀이

먼저 어떤 알약을 먹을 지 말지 결정하는 것은 특정 알약이 가능해지는 시기에만 하면 된다.

현재 특정 알약을 먹고 있고, 그 비율을 $s$라고 하자. 남아있는 신체 시간이 $K$라고 했을 때, 어떤 알약으로 갈아타면 이득이라는 뜻은 $sK < s'(K-c)$라는 뜻이다. 여기서 $s'$는 새로운 알약의 비율이다. 즉, 갈아타는 게 이득이라면 가능한 시점에 바로 갈아타는 게 최선이고 그렇지 않다면 갈아타지 않는게 낫다는 뜻이다.

그런데 이 가능해지는 시점에 남은 시간 $K$는 이전에 어떤 알약을 먹었냐에 따라서 달라집니다. 따라서, 그리디한 방법으론 안됩니다.

알약을 갈아탈지 말지를 정하는 시점은 알약이 사용 가능해지는 시점입니다.

그러면 우리가 관리해야할 시점은 신체 나이 기준으로 각 알약이 언제 가능해지는지가 됩니다. 그러니까, 알약이 가능해지는 시점이라고 주어진 $t_i$는 실제 시간 기준입니다. 그러나 알약을 잘 먹어서 신체 나이보다 많게 잘 살고 있다면 가능해질 시기의 신체 나이와 $t_i$를 비교하면 신체 나이가 적을 것입니다.

이제 이런 점을 고려해서 다음과 같은 dp를 생각해봅시다.
$$
dp(t)=\text{신체 나이가 t일 때 살 수 있는 최장 시간}
$$
그리고 $k_i : t_i = dp(k_i)$로 $k_i$를 정의합시다. i번째 알약이 사용가능 해질 때의 시각 $t_i$에서 가능한 가장 작은 신체나이입니다. 그리고 $i$번째 알약의 비율을 $p_i$라고 합시다.

그러면 dp 식을 이렇게 세워볼 수 있습니다.
$$
dp(t) = \underset{t_i<t}{max}(dp(t_i)+(t-(k_i+c))p_i)
$$
이제 CHT를 사용할 수 있습니다. 식을 좀 더 다르게 세우거나 하면 좀 이쁘게 정리가 가능하고 모든 기울기도 알 수 있는 형태가 나오는거 같습니다.

그러나, 팀연습 중에 그게 안되가지고 좀 꼬아서 꼬아서 간 거 같습니다.

어쨌든 제 코드는 Dynamic Convex Hull Trick을 이용해서 $O(PlogP)$에다가 $k_i$를 구하는 데에 실수 이분탐색을 사용해서 대략 $O(PlogPlogN)$이 걸린거 같습니다.

#include<bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;

ll N, P, C;

struct pill{
    ld slope;
    ll t;
    pill() {};
    pill(ld slope_, ll t_) : slope(slope_), t(t_) {};
};

const ld inf = 1/.0;

struct cht_line{
    ld m, b;
    mutable function<const cht_line *()> succ;
    bool operator<(const cht_line &rhs) const {
        if(rhs.b != inf) return m < rhs.m;
        const cht_line *s = succ();
        if(!s) return false;
        ld x = rhs.m;
        return b - s->b < (s->m - m) * x;
    }
};

struct max_hull : public multiset<cht_line> {
    bool bad(iterator y) {
        auto z = next(y);
        if(y == begin()) {
            if(z == end()) return false;
            return (y->m == z->m) && (y->b <= z->b);
        }
        auto x = prev(y);
        if(z == end()) return (y->m == x->m) && (y->b <= x->b);
        return (x->b - y->b) * (z->m - y->m) >= (y->b - z->b) * (y->m - x->m);
    }
    void insert_line(ld m, ld b) {
        auto y = insert((cht_line) {m,b});
        if(bad(y)) {
            erase(y); return ;
        }
        while((next(y) != end()) && bad(next(y))) erase(next(y));
        y->succ = [=] { return (next(y) == end()) ? 0 : &*next(y);};
        while((y != begin()) && bad(prev(y))) erase(prev(y));
        if(y != begin()) prev(y)->succ = [=] { return &*y; };
    }

    ld eval(ld x) {
        auto l = *lower_bound((cht_line) {x, inf});
        return l.m * x + l.b;
    }
};

vector<pill> v;
ld dp1[100005];
ld dp2[100005];
ld dp[100005];
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> P >> C;
    v.push_back(pill(1.0,0));
    for(int i=0;i<P;++i) {
        ll t; ld x, y;
        cin >> t >> x >> y;
        v.push_back(pill(x/y, t));
    }
    v.push_back(pill(0,N));
    dp[0] = 0;
    max_hull hull;
    hull.insert_line(v[0].slope,dp[0]);
    ld prev_time = 0;
    for(int i=1;i<=P;++i) {
        ld avail_time = v[i].t;
        for(int k=0;k<30;++k) {
            ld mid = (avail_time+prev_time)/2;
            if(hull.eval(mid) < v[i].t) prev_time = mid;
            else avail_time = mid;
        }
        prev_time = avail_time;
        dp[i] = hull.eval(avail_time);
        hull.insert_line(v[i].slope, dp[i]-v[i].slope*(avail_time+C));
    }
    cout << fixed << setprecision(15) << hull.eval(N) << '\n';
    return 0; 
}