[종만북] 문제: NERD2
문제
정의 및 문제 설명
집합 $S$에 속하는 $n$개의 순서쌍$(p_i, q_i)(i = 1, \ldots, n)$ 가 주어지고, 서로 다른 순서쌍끼리는 $p$ 값과 $q$ 값이 서로 같지 않다고 가정합니다.
즉, 임의의 $i \neq j$에 대해 $p_i \neq p_j \quad \text{and} \quad q_i \neq q_j$ 가 성립합니다.
순서쌍 $(p_i, q_i)$가 순서쌍 $(p_j, q_j)$에 의해 지배된다고 정의합니다., 이를 $(p_i, q_i) \prec (p_j, q_j)$ 라고 표기합니다. 이 관계는 정확히 다음 조건이 만족될 때 성립합니다.
$p_i < p_j \quad \text \quad q_i < q_j.$
순서쌍 $(p_i, q_i)$가 비지배임은, 집합 $S$ 내의 다른 어떤 순서쌍 $(p_j, q_j)$ $(j \neq i)$에 대해 $(p_i, q_i) \prec (p_j, q_j)$ 가 성립하지 않는 경우를 말합니다.
비지배 순서쌍의 집합 $N$은 다음과 같이 정의됩니다.
$N = { (p_i, q_i) \in S \mid \nexists\, (p_j, q_j) \in S \text{ with } p_i < p_j \text{ and } q_i < q_j }.$
| $ | N | $을 구하시오. |
서론
비 지배 순서쌍의 개수를 각 순서쌍이 추가될 때마다 세는 문제를 풀어봅시다.
이것을 풀기 위해 BST를 이용해서 풀고, Red-Black Tree로 구성된 std::map를 이용해 문제를 풀어봅시다.
알고리즘 구상
아이디어
어떤 순서쌍 $(p,q)$가 추가되려고 하면, 순서쌍 집합에서 $p$의 바로 오른쪽 순서쌍 $(p’,q’)$이 있고 $q < q’$이면 지배당하는 것임을 알 수 있습니다.
| 이후 이것이 지배당하지 않는 순서쌍이라면 순서쌍 집합에서 지배당하는 순서쌍을 파악해 제거를 해주고, 삽입됬을 때의 $ | N | $을 구하면 되는 문제입니다. |
naive 하게 접근
정렬된 배열을 이용하면 될 것 같은데, 그러면 $O(n^2)$의 시간이 걸립니다. $(1 \leq n \leq 50000)$이여서 이 알고리즘은 못 쓰겠네요.
BST를 왜 씀?
사실 BST는 정렬된 배열에 비해 장점이 하나도 없습니다.
정렬된 배열이 이진탐색을 하는 것과, BST가 재귀적 탐색을 하는 것은 단순히 BST가 오버헤드가 더 발생하는 것 말고는 장점이 하나도 없습니다.
그런데, 값이 추가되고 제거되는 상황이라면 이야기가 다릅니다.
정렬된 배열: $O(n)$의 시간, 트리: $O(\log n)$의 시간이 걸리기 때문입니다.
따라서 삽입, 제거를 $O(n \log n)$시간 안에 구현할 수 있습니다.
실수했던 부분
순서쌍이 추가되면 집합에 있던 어떤 순서쌍이 사라지는게 1대1 대응인줄 알았으나 사실 여러 개가 사라질 수 있어서 집합의 모든 원소에 대해 제거하는 함수를 작성해야 했습니다.
알고리즘 설계
핵심인 삽입 알고리즘을 설계해보자.
$(p,q)$가 집합 내의 임의의 순서쌍에 대해 지배당하면, 당연히 삽입할 필요가 없다.
만약 지배당하지 않는다면, 삽입되는 $(p,q)$에 대해 지배당하는 순서쌍을 제거한다.
알고리즘 구현
isContained()
삽입 알고리즘에서 순서쌍 집합 내의 임의의 점에 대해 $(p,q)$가 지배되는지 판단하는 함수를 구현한다.
1
2
3
4
5
bool isDominated(int p, int q) {
map<int, int>::iterator it = tree.lower_bound(p);
if (it == tree.end()) return false;
return q < it->second;
}
removeDominated()
삽입 알고리즘에서, 지배당하는 순서쌍을 전부 제거하는 함수를 구현한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void removeDominated(int p, int q) {
map<int, int>::iterator it = tree.lower_bound(p);
if (it == tree.begin()) return;
--it;
while (1) {
if (it->second > q) break; // 지배되지 않아서 종료
if (it == tree.begin()) {
tree.erase(it);
break; // 시작에 도착하면 종료
} else {
map<int, int>::iterator jt = it;
jt--;
tree.erase(it);
it = jt; // 지움
}
}
}
registered()
삽입 알고리즘을 구현한다.
- $(p,q)$가 지배 당한다면 삽입하지 않는다.
- 지배당하지 않으면, 우선 $(p,q)$에 지배당하는 점을 전부 제거 후 삽입.
1
2
3
4
5
6
int registered(int p, int q) {
if (isDominated(p, q)) return tree.size();
removeDominated(p, q);
tree[p] = q;
return tree.size();
}
main()
위에서 작성된 함수를 이용하여 알고리즘을 구현한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main() {
fastIO;
int C, n;
cin >> C;
while (C--) {
cin >> n;
tree.clear();
int sum = 0, p, q;
for (int i = 0; i < n; i++) {
cin >> p >> q;
sum += registered(p, q);
}
cout << sum << "\n";
}
return 0;
}
최종 코드
여기에서 확인하세요!