백준25055 Il Derby della Madonnina

작성일 | In

문제 링크

  • http://icpc.me/

문제 출처

  • 2021-2022 SWERC C번

사용 알고리즘

  • DP
  • 세그먼트 트리

시간복잡도

  • $O(N \log N)$

풀이

$O(N^2)$ DP 풀이는 쉽고 이걸 빠르게 계산해야 하는 것이 문제입니다. 자료구조로 최적화하려고 하면 부등식 3개가 나와서 2D Segment Tree를 사용해야 한다는 결론에 도달하게 됩니다. 더 효율적으로 해결하기 위해서는 문제에서 주어진 식을 잘 변형해야 합니다.

$s$에서 $e$로 이동하기 위해서는 $\frac{\vert A_e-A_s\vert}{T_e-T_s} \leq v$를 만족해야 합니다. 각 이벤트를 2차원 평면에 $(T_i, A_i)$ 형태로 플로팅하면, $x$ 좌표가 더 크고 기울기의 절댓값이 $v$ 이하인 점으로 이동할 수 있다는 것과 동치입니다.

만약 $v = 1$이면 이동 가능한 각도의 범위가 $[-45\degree, 45\degree]$이므로, 45도 회전시키면 이동 조건이 $X_s \leq X_e \land Y_s \leq Y_e$로 바뀝니다. 이런 제약 조건에서는 점을 $x$좌표 오름차순으로 정렬한 다음 $y$좌표의 LIS를 구하면 $O(N \log N)$에 해결할 수 있습니다.
$v \neq 1$이면 $x$좌표를 $v$배 늘려서 $v = 1$인 상황으로 만들 수 있습니다. 따라서 $O(N \log N)$ 시간에 문제를 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, V, T[202020], A[202020];
vector<pair<ll,ll>> P;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> V;
    for(int i=1; i<=N; i++) cin >> T[i];
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) P.emplace_back(V * T[i] - A[i], V * T[i] + A[i]);
    sort(P.begin(), P.end());

    vector<ll> lis;
    for(auto [x,y] : P){
        if(x < 0 || y < 0) continue;
        if(lis.empty() || lis.back() <= y) lis.push_back(y);
        else *upper_bound(lis.begin(), lis.end(), y) = y;
    }
    cout << lis.size();
}