Codeforces Round 990 (Div. 2)

(버추얼 참가)

문제풀이

A. Alyona and a Square Jigsaw Puzzle

Alyona 가 happy한 경우는 퍼즐의 크기가 홀수의 제곱수, 즉, $1, 9, 25, ...$ 일 때이다. 주어진 $a$를 차례로 더해나가면서 퍼즐의 크기가 홀수의 제곱수가 되는지 체크해주면 된다. 체크 방법은 현재 단계의 $a$합을 제곱근한 후 홀수인지 체크하고, 다시 제곱했을때 원래 수가 되는지 보면 된다. 아니면 $n$이 충분히 작기 때문에 브루트포스를 사용해도 된다.

B. Replace Character

중복 원소를 포함하는 순열의 개수는 다음과 같다:

$N$은 전체 원소 개수, $k_i$는 구분되는 $i$번째 원소의 개수이다. 우리가 할 수 있는 연산은 $i,j$를 정한 후, $k_i:=k_i-1, k_j:=k_j+1$를 하는 것이라고 바꾸어 볼 수 있다. 위의 식이 최소화 되는 $i,j$를 정해야 하므로 가장 가장 작은 $k_i$, 가장 큰 $k_j$를 고르는 것이 언제나 최적이다.

C. Swap Columns and Find a Path

아래로 한칸 이동하는 것은 경로상 한번만 존재할 수 있다는 점에 집중하자. 범위 $[1, N]$에 있는 모든 칸에 대해서 해당 칸에서 아래로 내려가는 경우에 점수 최대치를 브루트 포스할 것이다. $Lmax_i$를 $\sum_{j=1}^{i}a_{1,j}$의 최대치로, $Rmax_i$를 $\sum_{j=i}^{N}a_{2,j}$의 최대치라고 두고 모두 전처리 해두자. $Lmax, Rmax$를 계산 하는것은 아주 쉬운데, $i$번째 열의 스왑할지 말지 결정할때 단순히 $a_{1,i}, a_{2,i}$중 큰것을 택하기만 하면 된다. 정답은 $max_{i=1}^{N}(Lmax_{i-1}+Rmax_{i+1}+a_{1,i}+a_{2,i})$가 된다.

D. Move Back at a Cost

가장 중요한 관찰은 원소를 뒤로 옮기는 연산을 할때, 연산 순서를 유연하게 변경할 수 있기 때문에, 단일 원소에는 연산이 최대 1번만 적용하는것이 최적이라는 것이다.

그렇다면 어떤 원소를 움직이는게 좋을까를 생각해봐야 한다. 우선 우리는 사전순으로 최소인 수열을 얻길 원하므로, 수열을 왼쪽에서 오른쪽으로 읽어나가며 사용할 수 있는 가장 작은 숫자를 선택한다. 예를 들어 예제의 두번째 테스트 케이스를 살펴보면 $[1, 2, 2, 1, 4] \rarr [1,1]$ 과 같이 된다. 중간에 $2$가 선택되지 않은 이유는 4번째에 사용할 수 있는 $1$이 남아있기 때문이다. 우선순위큐등을 사용하면 사용할 수 있는 숫자중 최소값을 얻는 것이 쉽다.

남아있는 숫자들 중 선택된 가장 나중 숫자 앞의 숫자들(그룹 $A$)은 연산이 적용되어 값이 $+1$되는 대신 위치 선정이 자유롭다. 남아있는 숫자들 중 선택된 가중 나중 숫자 뒤에 위치하는 숫자들(그룹 $B$)은 연산이 적용될수도, 아닐수도 있다. 그룹 $B$의 원소들을 왼쪽부터 오른쪽으로 읽어가면서 그룹 $A$의 가장 작은 원소와 같거나 작다면 연산을 적용하지 않고 그대로 정답 배열에 더해주면 된다. 아닌 경우에는 뒤에 위치하는 모든 $B$의 원소들도 연산을 적용하는 것이 최적이라고 할 수 있다.

E. Adventurers

upsolved

우선 좌표의 범위가 $-10^9 \leq x_i,y _i \leq 10^9$이라, 좌표압축을 수행한다. 그리고 어떤 한 축, 일반 성을 잃지 않고 $Y$축이라고 하자. 모든 $Y$축 선택에 대해서 최적해를 구할 것이다. 좌표압축을 수행했기 때문에 $Y$축을 선택하는 방법은 최악의 경우에도 $N$가지이다.

$Y$축을 고정했으면, $X$축을 선택해야 하는데, 여기서는 답을 이분탐색할 수 있다. 그렇다면 답 $k$가 가능한지 아닌지 결정 문제가 부분문제로 남게되는데, 이는 어떻게 해결할까? 우선 고정된 Y축으로 이미 점들이 두 그룹으로 나뉘는데, 간편하게 축 왼쪽에 있는 그룹은 $L$, 축에 겹치거나 오른쪽에 있는 그룹은 $R$이라고 볼 것이다. 그리고 각 그룹마다 $Y$좌표마다 존재하는 점들의 개수를 세그먼트 트리로 관리할 것이다. $L$그룹을 다시 $X$축을 설정하여 나눴을때 나눠진 각 그룹의 크기가 최소 $k$인지 체크하면 된다. 이는 세그먼트 트리 위에서의 이분탐색을 사용하면 로그 시간복잡도에 가능하다. 그럼 $L$그룹에 대해서 설정가능한 $X$축의 $y$좌표 범위가 나온다. $R$그룹에 대해서도 마찬가지로 수행하고, $R$그룹에 대해서도 설정가능한 $X$축의 $y$좌표 범위가 나올 것이다. 이 두 범위의 교집합이 발생한다면 가장 작은 그룹의 크기가 최소 $k$인 자르기 방법을 찾아 낸 것이라고 할 수 있다. 이를 모든 $Y$축 선택에 대해서 수행하면 된다.

$Y$축은 압축된 좌표상에서 +1씩 더해가며 설정하고, $Y$좌표가 1씩 더해질때마다 $Y$축 경계에 있는 점들은 $R$그룹에서 $L$그룹으로 넘겨주기만 하면 된다.

총 시간복잡도는 $\mathcal{O}(N\log^2 N)$이다.

• 세그먼트 트리 위에서 이분탐색을 나이브하게 로그 제곱에 구현했다면 시간 초과를 받을 확률이 크다. 생각보다 자주 나오는 토픽이라, 따로 공부해두면 좋다. 필자는 AtCoder library 의 세그먼트 트리 구현체를 즐겨 사용하는데, 미리 구현되어있는 이분탐색 함수인 max_right(), min_left() 함수를 사용하였다. 비재귀 구현체라 성능이 굉장하다.

F. For the Emperor!

N/A

총평

근래 버추얼이나 실제로 참가했던 콘테스트중에 C는 역대급으로 쉬운 문제에 해당했다. 특히 C는 평소에 Div.2 C 난이도를 얼추 몸으로 알고 있는 상태였는데 너무 단순 구현문제여서, 내가 문제를 제대로 이해한것이 맞는지부터 의심이 들었다.

문제가 쉬운것도 있지만, 쉬운문제를 이제 꽤 빨리 풀어내고 있다는 사실이 고무적이다. 예전에는 A, B번에 대한 공포가 있었는데 지금은 오히려 C, D번이 더 무섭다. 이번 라운드는 예외였지만 C번 풀이 시간을 조금 더 최적화 해야할 것 같다.