[BOJ/C++] 23744. 알고리즘 과외

문제 링크 : https://www.acmicpc.net/problem/23744

23744번: 알고리즘 과외

 

1. 설명

N명의 학생이 있고, 각각 레이팅 값이 있습니다.

레이팅 차가 최대가 되도록 2명을 뽑아 그 차를 구해야 하는데, 학생마다 짝이 될 수 있는 학생 번호의 구간이 다릅니다.

 

2. 풀이

2021 서강대 프로그래밍 대회에서 출제된 문제입니다. 공식 홈페이지에 풀이가 있습니다.

 

$i$번째 학생과 짝을 이룰 수 있는 학생 번호의 구간은 $[i - r_i, i - l_i]$과 $[i+l_i , i+r_i]$입니다.

편의를 위해 레이팅이 최대가 되는 두 학생이 $x, i (x \lt i)$라고 합시다.

$i$번째 학생에 대해, 레이팅 차가 최대가 되는 학생은 $i - r_i \le x \le i - l_i$인 $x$번째 학생이며, 레이팅 $a_x$가 이 구간에서 최소 혹은 최대일 것을 알 수 있습니다.

다시 말하면 $[l_i, r_i]$ 구간에서 최솟값, 최댓값을 찾는 쿼리를 실행한다는 것이 됩니다. 세그먼트 트리죠.

 

다만 단순히 최솟값, 최댓값 $x$을 구한다면, $x$에 대해서도 조건 $x+l_x \le i \le x+r_x$를 만족하는지 알 수 없습니다. 이 경우를 위한 처리를 해주어야 합니다.

 

모든 $j \lt i$에 대해, $j + l_j$와 $j + r_j + 1$를 계산해봅시다.

$i = j + l_j$를 만족하는 $i$는 $j$번째 학생이 짝을 이룰 수 있는 첫 번째 학생의 번호입니다.

$i = j + r_j + 1$을 만족하는 $i$는 $j$번째 학생이 짝을 이룰 수 없게 되는 첫 번째 학생의 번호입니다.

그러니 모든 $0 \le i \lt N$에 대해 $i$를 증가시키면서 위 두 조건을 체크하면, $j$번째 학생과 짝을 이룰 수 있는지 확인할 수 있습니다.

 

일일이 모든 $i$에 대해 모든 $j$를 확인하는 건 비효율적이니, ($O(N^2)$)

정렬을 한 뒤에 차례대로 체크해줍시다. 코드를 확인하시는 게 이해가 더 빠를지도 모르겠습니다.

 

정리하면, $i$번째 학생과 짝을 이루는 학생들 중 레이팅의 차의 최대값을 구하려고 합니다.

초기 상태에는 어떠한 학생과도 짝을 이룰 수 없도록 세그먼트 트리를 초기화해야 합니다.

$\min = \infty , \max = -\infty$로 초기화하면 됩니다.

 

$j + l_j = i$인 $j$에 대해 $j$번째 학생에 해당하는 노드의 최솟값/최댓값을 $a[j]$로 업데이트합니다.

$j + r_j + 1 = i$인 $j$에 대해서는, 다시 $\infty , -\infty$로 업데이트합니다.

 

그 후에 가능한 최솟값 $m$, 최댓값 $M$을 구해서 차의 최댓값을 구하면 됩니다.

$ans = \max(M - a[i], a[i] - m)$

 

결과값이 음수라면 ($ans$의 초기값이 음수라는 가정 하에) 짝을 이룰 수 있는 경우가 존재하지 않는 것이므로 -1을 출력하면 됩니다.

이렇게 하면 $O(N log N)$에 문제를 풀 수 있습니다.

 

3. 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> p;

const int INF = 1e9 + 5;
int N, a[200001];
p range[200001];

struct segTree
{
	p v[1 << 19];

	p update(int node, int start, int end, int index, int minval, int maxval)
	{
		if (index < start || index > end) return v[node];

		if (start != end)
		{
			int mid = (start + end) >> 1;
			p u1 = update(node << 1, start, mid, index, minval, maxval), u2 = update(node << 1 | 1, mid + 1, end, index, minval, maxval);
			return v[node] = { min(u1.first, u2.first), max(u1.second, u2.second) };
		}
		else return v[node] = { minval, maxval };
	}

	p query(int index, int start, int end, int left, int right)
	{
		if (left > end || right < start) return { INF, -INF };
		if (left <= start && end <= right) return v[index];

		int mid = (start + end) >> 1;

		p q1 = query(index << 1, start, mid, left, right), q2 = query(index << 1 | 1, mid + 1, end, left, right);
		return { min(q1.first, q2.first), max(q1.second, q2.second) };
	}
};

int ans = -1;
segTree tree;
p q;
priority_queue<p, vector<p>, greater<p>> L, R;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> a[i] >> range[i].first >> range[i].second;
		L.emplace(i + range[i].first, i);
		R.emplace(i + range[i].second + 1, i);
		tree.update(1, 0, N - 1, i, INF, -INF);
	}

	for (int i = 0; i < N; i++)
	{
		while (L.size() && L.top().first == i)
		{
			int j = L.top().second;
			tree.update(1, 0, N - 1, j, a[j], a[j]);
			L.pop();
		}

		while (R.size() && R.top().first == i)
		{
			tree.update(1, 0, N - 1, R.top().second, INF, -INF);
			R.pop();
		}

		q = tree.query(1, 0, N - 1, i - range[i].second, i - range[i].first);
		ans = max(ans, max(q.second - a[i], a[i] - q.first));
	}

	cout << ans;
	return 0;
}

처음에는 INF 값을 2e9로 잡았다가 WA를 받아서 좀 헤맸습니다.

넉넉하게 잡는다고 그렇게 했는데, 값을 구하는 과정에서 오버플로우가 발생한다는 것을 알게 되었습니다.

(정확히는 언더플로우기는 합니다)

사실 $a_i$의 최댓값이 $10^9$이라서 레이팅의 차 또한 최댓값이 $10^9$입니다.

INF 값을 위 코드처럼 더 작게 잡아줘도 문제 없이 돌아갑니다.