L을 소가 달리기 시작하는 위치, R을 소가 달리기를 마치는 위치를 의미하는 알파벳으로 사용하겠다.
시간 T동안 소 A가 L1에서 R1까지, 소 B가 L2에서 R2까지 뛰었다고 해보자. (단, L1<L2)
그렇다면, R1<R2이면 두 소는 충돌하지 않고 뛸 것이고, 그렇지 않다면 충돌할 것이라는 것을 알 수 있다.
한편, 문제에서 구하는 lane 수는 어떤 두마리 소를 골라도 달리는 중에 충돌하게 되는 집합의 최대 크기를 구하는 문제로 생각할 수 있다. 이는, (서로 다른) L이 정렬되어 입력이 들어올 때 R값들의 순서를 역순으로 살펴서 찾을 수 있는 LIS의 길이와 같다는 것을 알 수 있다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
vector<pair<ll, int>> arr;
bool xcomp(pair<ll, int> p1, pair<ll, int> p2) {
if (p1.first != p2.first) return p1.first < p2.first;
return p1.second > p2.second;
}
bool icomp(pair<ll, int> p1, pair<ll, int> p2) {
return p1.second < p2.second;
}
int seg[262145];
int update(int L, int R, int qI, int qVal, int sI) {
if (R < qI || qI < L) return seg[sI];
if (L == R) return seg[sI] = qVal;
return seg[sI] = max(update(L, (L + R) / 2, qI, qVal, sI * 2), update((L + R) / 2 + 1, R, qI, qVal, sI * 2 + 1));
}
int rangemax(int L, int R, int qL, int qR, int sI) {
if (R < qL || qR < L) return 0;
if (qL <= L && R <= qR) return seg[sI];
return max(rangemax(L, (L + R) / 2, qL, qR, sI * 2), rangemax((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N; ll T; cin >> N >> T;
for (int i = 0; i < N; i++) {
ll x, v; cin >> x >> v;
arr.push_back({ x + v * T,i });
}
sort(arr.begin(), arr.end(), xcomp);
for (int i = 0; i < N; i++) {
arr[i].first = i + 1;
}
sort(arr.begin(), arr.end(), icomp);
int cnt = 0;
for (auto iter = arr.rbegin(); iter != arr.rend(); iter++) {
int temp = rangemax(1, N, 1, (*iter).first, 1) + 1;
if (temp > cnt) cnt = temp;
update(1, N, (*iter).first, temp, 1);
}
cout << cnt;
}
최소한의 전깃줄을 지워 전깃줄이 교차하는 부분을 없앤다는 것은 최대한의 교차하지 않는 전깃줄을 남긴다는 말과 같다. 최대한의 교차하지 않는 전깃줄의 개수는 LIS를 구하는 것과 같다는 것을 알 수 있을 것이다.
따라서, LIS의 크기를 구하고 LIS를 역추적하여 아무거나 하나를 구한 다음 그 전선들을 제외한 나머지 전선들을 없애는 것으로 문제를 해결할 수 있다.
(세그먼트트리로 LIS 구하기 연습1)
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int parent[500001];
vector<pair<int,int>> arr;
int seg[1048577];
int update(int L, int R, int qI, int qVal, int sI) {
if (R < qI || qI < L) return seg[sI];
if (L == R) return seg[sI] = qVal;
return seg[sI] = max(update(L, (L + R) / 2, qI, qVal, sI * 2), update((L + R) / 2 + 1, R, qI, qVal, sI * 2 + 1));
}
int nth(int L, int R, int N) {
int sI = 1;
while (L < R) {
if (seg[sI * 2] < N) {
sI = sI * 2 + 1;
L = (L + R) / 2 + 1;
}
else {
sI = sI * 2;
R = (L + R) / 2;
}
}
return L;
}
int rangemax(int L, int R, int qL, int qR, int sI) {
if (qR < L || R < qL) return 0;
if (qL <= L && R <= qR) return seg[sI];
return max(rangemax(L, (L + R) / 2, qL, qR, sI * 2), rangemax((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N; cin >> N;
for (int i = 0; i < N; i++) {
int x, y; cin >> x >> y;
arr.push_back({ x,y });
}
sort(arr.begin(), arr.end());
int ans = 0;
int last;
for (auto node : arr) {
int x = node.second;
int temp = rangemax(1, 500000, 1, x, 1);
parent[x] = nth(1, 500000, temp);
temp++;
if (temp > ans) {
last = x;
ans = temp;
}
update(1, 500000, x, temp, 1);
}
for (int i = 0; i < ans; i++) {
int l = parent[last];
parent[last] = 9999999;
last = l;
}
cout << N - ans << '\n';
for (int i = 0; i < N; i++) {
if (parent[arr[i].second] < 999999) cout << arr[i].first << '\n';
}
}