Codeforces Round #905 (Div. 1)

레드가 가고 싶다던 Jeuti와 버츄얼을 돌았다.

그리고 같이 망했다.

https://codeforces.com/contest/1887

---

A1. Dances (Easy version) [00:07:42] *1400

Easy version 에서는 한 번만 비교해 주면 된다.

최적의 결과는 $A$와 $B$ 배열을 각각 정렬한 뒤, $A$의 Prefix와 $B$의 Suffix를 순서대로 매칭시켜 봄으로써 얻을 수 있다. 이제 답에 대한 이분 탐색을 하면 $O(NlogN)$에 풀 수 있다.

https://codeforces.com/contest/1887/submission/239066721

---

A2. Dances (Hard version) [00:50:19, -1] *1900

Hard version 에서는 $M$번이나 비교해야 한다.

배열에 더 큰 값이 있을수록 매칭을 시키는 것이 어려워진다. 따라서 $A_1$의 값에 따라 답이 단조적으로 감소함을 알 수 있다. 물론 $M$이 $10^9$이기 때문에, 답이 같은 구간 경계를 잘 찾아주는 것이 중요하다.

 

내가 대회 시간 내에 짰던 풀이는 다음과 같다.

답이 변할 수 있는 구간 후보는 $O(N)$개 존재한다. 왜냐면 $A$ 또는 $B$의 값이 변하는 지점 부근에서만 답이 달라질 수 있기 때문이다. 따라서 각 지점마다 답이 얼마나 변하는지를 빠르게 갱신할 수 있다면 전체 문제를 풀 수 있다.

 

답을 빠르게 계산하기 위해 다음과 같은 새로운 값을 구한다.

• $P_i$: $A_i$를 $B$에 매칭하기 위해 옮겨야 하는 최소 칸 수

항상 같은 위치에 있거나 더 오른쪽에 있는 수와 매칭시켜야 하므로 $P_i$는 $0$ 이상이고, $A_{i-1}$의 매칭 위치보다 더 오른쪽에 있어야 하기 때문에 $1 < i$일 때 $P_{i - 1} < P_i$를 만족해야 한다. 이를 만족하는 $P_i$의 값들은 $A_1 = 1$이라고 했을 때 이분 탐색을 이용해 총 $O(NlogN)$에 전처리를 해줄 수 있다.

$P$를 이용해 답을 계산하는 과정은 다음과 같다. 답이 $k$ 이상이라는 것은 $1 ~ k$ 사이의 모든 값들이 최대 $N - k$칸을 옮겨서 안에 매칭을 할 수 있다는 말과 같다. 따라서 $P$의 Prefix Max 값을 잘 찾을 수 있다면 답을 구할 수 있다.

이제 모든 구간 경계의 후보를 오름차순으로 정렬한 뒤, 각 후보에 대해 하나씩 답을 계산한다. 값이 증가할 때마다 오른쪽으로 한 칸씩 이동하니, 위치가 갱신될 때마다 $P$의 값도 같이 경신해 줄 수 있다. 이러면 전체 문제를 $O(NlogN)$에 해결가능하다.

https://codeforces.com/contest/1887/submission/239067206

---

사실 답은 최대 $1$ 변한다. 애초에 정렬했을 때 원래 위치에서 최대 한 칸까지 밖에 못 움직이기 때문이다. 그래서 답이 변하는 지점을 이분 탐색으로 찾아줘도 무방하다. 이러면 $O(NlogNlogM)$에 문제를 해결할 수 있다. 역시 머리가 나쁘면 몸이 고생한다는 것을 느꼈다.

https://codeforces.com/contest/1887/submission/239074208

---

B. Time Travel [01:14:30] *1900

한 정점에서 그대로 머무르는 것이 가능하기 때문에, 이전에 방문한 정점을 다시 방문할 필요가 없다. 따라서 하나의 간선도 최대 한 번만 방문이 가능하다.

이를 구현하기 위해서는 거리는 전역으로 관리하되, 각 시간마다 큐를 하나씩 둔다. 이동할 때는 그 정점이 속한 모든 시간대에서 이동해야 하고, 이동의 결과로 다음 정점을 넣을 때도 다음 정점이 속한 모든 시간대의 큐에 하나씩 넣어줘야 한다.

https://codeforces.com/contest/1887/submission/239067399

---

C. Minimum Array [Upsolved] *2400

$i$번 쿼리까지 완료한 시점과 $j, (i < j)$번 쿼리까지 완료한 시점 중, 어떤 시점이 사전순으로 더 최소인지 비교하기 위해서는 $[i + 1, j]$번 쿼리 사이의 변화값을 알고 있으면 된다. 가장 처음으로 등장하는 $0$이 아닌 값이 음수면 $j$가 사전순으로 더 작고, 양수면 $i$가 사전순으로 더 크다.

이 사실을 이용하면 답을 그리디하게 구할 수 있다. 기본적으로는 쿼리를 그대로 시뮬레이션하면서, 이분 탐색을 이용해 값이 $0$이 아닌 첫 지점을 찾는다. 그리고 새로운 사전순 최소가 되는 지점을 찾을 때마다 세그먼트 트리를 다시 리셋해 주면 된다. $O(N + QlogN)$에 문제를 해결할 수 있다.

 

레이지 세그먼트 트리를 쓰지 않고도 문제를 해결할 수 있다. $D_i = A_{i + 1} - A_i$로 정의한 차수열을 생각해보자. 원본 배열 $A$와 차수열 $D$의 사전순 정렬 순서는 동일하기 때문에, $D$에서 문제를 해결해 줘도 동일하게 답을 구할 수 있다.

이렇게 문제를 변환했을 때의 좋은 점은 Range Update를 Point Update로 바꿀 수 있기 때문에 set과 같은 BBST를 이용해서 시뮬레이션을 할 수 있다는 것이다. 시간복잡도는 세그먼트 트리를 이용했을 때와 동일하고, 구현이 훨씬 쉽다.

https://codeforces.com/contest/1887/submission/238911008

---

D. Split [Upsolved] *2700

조건을 만족하는 Maximal한 구간들을 다 구해두고, 쿼리로 들어오는 구간이 미리 구해둔 구간 중 하나에 속하는지를 판별하는 식으로 문제를 해결한다. 이런 Maximal한 구간들을 구할 수 있다면, 쿼리를 처리하는 건 세그먼트 트리 들고 스위핑을 함으로써 구할 수 있다.

 

Maximal한 구간을 찾는 방법을 생각해 보자. 다음 값들을 알고 있을 때 $A_i$가 병목이 되면서 최대가 되는 구간의 길이를 구할 수 있다. 병목이 된다는 것은 good 인 배열의 왼쪽 부분의 최댓값이 $A_i$가 됨을 의미한다고 하자.

1. $L_i$ = $i$보다 작으면서, $A_i$보다 큰 값 중 가장 오른쪽에 있는 값
2. $M_i$ = $i$보다 크면서, $A_i$보다 큰 값 중 가장 왼쪽에 있는 값
3. $R_i$ = $M_i$보다 크면서, $A_i$보다 작은 값 중 가장 왼쪽에 있는 값

이 값들은 모두 set을 들고 스위핑을 하면 어렵지 않게 구할 수 있다.

이때 $A_i$가 병목이 되는 구간 중 Maximal한 구간은 $[L_i + 1, R_i - 1]$가 된다. 단, 구간은 반드시 $M_i - 1$과 $M_i$를 지나야 한다. 즉, 구간의 왼쪽 $l$은 $L_i < l < M_i$을, 오른쪽 $r$은 $M_i \le r < R_i$를 만족해야 한다.

$l$이 위치할 수 있는 구간을 2차원 좌표평면의 $x$축으로, $r$이 위치할 수 있는 구간을 2차원 좌표평면의 $y$축으로 생각하면 직사각형 영역이 생긴다. 그러면 쿼리로 들어온 점이 직사각형 안에 위치하는가? 를 묻는 문제로 변환되고, 위에서 언급한 것과 같이 세그먼트 트리와 스위핑을 이용해 해결할 수 있다.

https://codeforces.com/contest/1887/submission/239019330

---

E. Good Colorings [Upsolved] *3100
색칠된 칸을 행과 열을 잇는 간선으로 생각하자. 이렇게 만든 그래프는 $2N$개의 정점과 $2N$개의 간선을 가진 이분 그래프가 된다. 그리고 문제에서 찾고자 하는 네 개의 색칠된 칸은 간선의 색이 모두 다르면서, 길이가 $4$인 사이클을 찾는 것이 된다.

 

우선 항상 조건을 만족하는 길이 $4$의 사이클을 만들 수 있음을 보인다. 직사각형 한 칸을 색칠하게 되면 사이클이 사이클 하나가 두 개로 나뉘게 된다. 이때, 원본 사이클을 구성하는 간선의 색깔은 모두 다르기 때문에, 인터랙터가 어떤 색깔로 새로 들어온 간선을 색칠하든 간에 원래 사이클보다 길이가 더 작으면서, 모든 간선의 색깔이 다른 사이클을 구성하는 것이 가능하다. 이렇게 문제를 축소시켜 나가다 보면 언젠가는 사이클의 길이가 $4$에 도달하게 되고, 문제를 해결할 수 있다.

 

사이클을 나눌 때, 항상 사이클의 크기가 절반이 되도록 나누면 길이가 $log$ 스케일로 감소하기 때문에, 열 번의 쿼리 안에 조건을 만족하는 직사각형을 무조건 만들 수 있다.

https://codeforces.com/contest/1887/submission/239042886