Codeforces Round 997 (Div. 2) D. Unique Median

 

 

문제 링크

• Problem - D - Codeforces

 

문제 풀이

 

마지막 포스팅 이후, 2개월 만에 문제풀이를 쓰는 것 같다. 오랜만에 코드포스도 쳤겠다... 요즘 저조한 퍼포먼스로 초심을 되찾고자 업솔빙 포스팅을 자세하게 적어보고자 한다. 대회 중부터 쭉 붙잡다가 2 시간 걸려서 푼 문제다.

 

이 글에 적은 풀이보다 더 쉬운 방법은, 조건에 맞지 않는 부분배열 B를 찾는 것이다. 하지만, 대회 때는 조건에 맞는 부분배열 B를 모두 찾는 것에 혈안이 되어, 이 부분을 놓치게 되었다.

 

문제. 배열 $A = [a_1, a_2, \cdots , a_N]$ 이 주어질 때, 배열 A의 부분배열 B가 다음을 만족할 때, 부분 배열 B의 개수를 찾아라.

 부분배열의 크기를 $m$이라고 하자. A의 정렬 된 부분배열 B의 $\big\lfloor \frac{m+1}{2} \big\rfloor$ 와 $\big\lceil\frac{m+1}{2} \big\rceil$ 번째 수가 같아야 한다.

 

배열 A의 크기가 1e5이기 때문에, 웬만한 나이브로는 풀리지 않는다. 하지만, $a_i$가 1에서 10사이의 수이다.

이 부분은 진짜로 상당히 수상하다. 그래서, 나는 1부터 10까지 경우를 보며, 각각의 수가 가운데의 두 수 또는 하나의 수가 될 수 있게 만들어 보기로 했다.

 

예를 들어, 5를 중심으로 살펴보자. 배열 A를 5를 중심으로, 5보다 작은 수, 5보다 큰 수, 그리고 5인 수 3개로 나눌 수 있다.

이렇게 문제를 바꾸고, 가운데 수가 5가 될 수 있는 부분배열을 만드는데 집중해보자.

 

global x = 0, y = 0 일 때, 오른쪽에서 부터 왼쪽으로 배열을 만들었을 때, 가지고 있는 값 쌍

 

말 그대로, 배열은 다음과 같이, 5보다 큰 수 (빨간색 화살표), 5보다 작은 수 (파란색 화살표)가 될 것이다. 이때, 5는 두 번째 쌍에 만날 때마다 1씩 추가로 올려주고, 다른 값들을 만났을 때는 크기 유무에 따라 플마 1을 해준다.

 

자 우리의 문제 풀이 목표를 다시 세팅해 보자.

 

우리는 인덱스를 0번째부터 N-1번째까지 순서대로 보며, 봤던 인덱스는 전처리 해둔다. 특정 인덱스 $x$에서, 부분배열의 가장 왼쪽 인덱스를 $[0, x-1]$ 값으로, 오른쪽 인덱스를 x로 하는 부분배열 B가 몇 개 있는지 빠른 시간 내에 찾을 수 있다면, 문제를 해결할 수 있다.

 

위의 순서 쌍 (x, y)로 값을 전처리 해두면, 그래프 $y = |x|$ 보다 위에 있을 때, 그 순서쌍을 가지고 있는 인덱스는 부분배열의 조건을 만족한다.

 

왜냐하면, y는 5의 개수이다. $|x|$는 5보다 크거나 작은 값들 중, 어느 한쪽이 더 많을 때의 갯수이다. 5가 중앙값이 되기 위해서는, 이 값들을 상쇄시키고 나서 y값이 남아 있어야 한다.

 

따라서, 순서 쌍 (x, y)에 대하여, $ (x, y) \longrightarrow (y > |x|)$ 를 만족할 때, 그 순서쌍을 가지고 있는 인덱스까지 부분배열을 만들면, 그 부분배열은 5를 중앙값으로 가지는 부분배열이 되게 된다.

 

하지만, 이러면, 한 인덱스에서 왼쪽 구간 전체를 업데이트해야 하므로, 한 번에 O(N)의 시간복잡도가 발생하게 된다. 이런 류의 문제는 Atcoder에서 흔히 나오는 전역 상태 관리 문제이며, 전역 변수를 둠으로써 간단하게 해결할 수 있다.

 

이 부분은 설명하게 되면 너무 복잡하다. 단순히, 수의 크기 관계만 따진다고 할 때, 한 배열 빼고 모든 배열에 1을 더하는 것은 한 배열만 -1을 하는 것 과 같다는 논리를 이용한다.

 

즉, 오른쪽으로 스위핑을 진행하면서, 5를 만났다면, 기존 전처리된 순서쌍의 값 두 번째에 +1을 할게 아니라, 본인의 순서쌍 값 두 번째에 -1을 하면 된다는 것이다.

 

이를 응용하면, 다음과 같은 연장된 배열을 만들 수 있다.

전역 상태가 (0, -2) 인 연장 된 배열

 

전역 상태가 (0, -2)로 달라졌기 때문에, 우리는 새로운 조건을 만족하는 순서쌍들을 찾아야 한다. $y = |x - 0| - 2$ 가 새로운 조건이 되게 되며, $ (x, y) \longrightarrow (y > |x - 0| - 2)$ 를 만족하는 순서쌍들을 찾으면 된다.

 

각 인덱스에 순서쌍 값을 끝까지 일단 만들었다고 하자. 이때 정답을 일반화된 수식으로 적어보자.

 

인덱스 i번째 (0-based) 순서쌍을 $p_i$ 라고 하고 첫 번째 값을 $p_i[0]$ 두 번째를 $p_i[1]$ 이라고 하자.

 

$$
\sum_{i = 1}^N 
\sum_{j = 0}^{i-1} 
\begin{cases} 
1, & \text{if } \big\lvert p_j[0] - p_i[0] \big\rvert + p_i[1] < p_j[1] \\ 
0, & \text{otherwise} 
\end{cases}
$$

 

이를 무작정, 코드로 옮기면, 당연히 O$(N^2)$로 시간초과 박살이 난다.

 

정답을 기록할 때는 어떤 순서쌍을 전역상태로 사용하고 $ y = |x| $ 평행이동 시켜서, 조건에 만족하는 것을 찾는다고 볼 수 있다. 좌표평면에 시각적으로 생각을 해보면, 미리 점을 다 찍어놓고, 각 점에서, $ y = |x|$ 개형의 그래프를 그리고 그 위의 점들을 각각 세는 것과 같다.

 

그래그래... 그래서? 어떻게 이와 같은 작업을 빠르게 할 수 있을까?

 

대각좌표를 기준으로 하고 있는데, 이것을 잘 변환하여, 대각 좌표들을 x 축과 y축에 평행하게 만들고, 2차원 쿼리를 날리면 수행시간을 줄일 수 있을 것이다.

 

파란선을 x축, 초록색을 y축으로...

 

점의 위치관계는 유지하면서, 해당 기준선으로 좌표를 잘 변환하면, 각 점 (x, y)에서, x좌표보다, y좌표보다 둘 다 큰 값을 가지고 있는 점 찾기 문제로 바꿀 수 있다.

 

컴퓨터공학과 학생이라면, 선형대수학을 배우게 되는데 이럴 때 쓰는 게 전공지식이다. 선형변환 매트릭스를 짜서 좌표평면을 선형변환 시켜 전체적으로 이동시키자. 이러면, 대각선에 관계된 점들이 x축과 y축으로 나란하게 옮겨지게 된다.

 

$$
\begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix}
\begin{bmatrix} x \\ y \end{bmatrix}
= \begin{bmatrix} x + y \\ -x + y \end{bmatrix}
$$ 

 

을 이용하면,  위의 사진과 같이 한 대각선의 점들을 x에 평행하게, y에 평행하게 변환시킬 수 있다. 이때, 물론 전체적인 거리 scale이 $\sqrt2$배가 되기 때문에, 큰 값 관리를 잘해주어야 한다.

 

이후, 전체적인 값 조정... 크기 관계만 볼 것이니.. 무지성 압축을 그냥 때려 박고...

 

자 그럼 이제 변환된 좌표에서 2차원 쿼리를 날리면 된다. 진짜 문제 하드하다.. (이것도 사실상 2차 본게임이다.)

사실상 자료구조만 해도 어마어마한 난이도.... 

 

나는 이분탐색과 구간 내에서 수를 구간탐색해 주는 자료구조인 Persistance Segment Tree를 응용하여 풀었다.

이 짓을 모든 수 1에서 10까지 해주면, 아주 잘 풀린다.

 

굉장히... 무거운 자료구조를 사용하여 O($10 N \log N$)을 만들었는데.. 시간초과를 몇 번 맞았다....;;;;

 

O($ 10 N \log^2 N$)는 잘 굴러가는지 모르겠다....?