[알고리즘] Codeforces Round #768 (Div. 2)

코드포스에 너무 어려움을 느껴 앞으로 editorial를 보고 공부하여 블로그에 정리하고자 한다..

(Div2 2솔까지는 할만한데 3솔부터 못해먹겠다.)

 

A - min max swap [Solved!]

두 배열 $a_1, a_2, ... , a_n$과 $b_1, b_2, ..., b_n$이 주어졌을 때 같은 인덱스들을 여러번 적절히 바꾸어 만들어진 새로운 두 배열을 만든다. 만들어진 각 배열의 최댓값을 곱했을 때 가능한 최솟값을 구하는 문제이다.

 

$a_i, b_i$를 비교하면서 두 수중 작은 값을 $a_i$, 큰 값을 $b_i$에 넣으면 최적해가 구해진다.

 

B - Fun with Even Subarrays [Solved!]

배열이 주어졌을 때 적당한 범위 $a_l, a_{l+1}, ..., a_r$을 정해서 $k = r-l+1$이라 할 때 $a_{i-k} = a_i$라 하자.($l \le i \le r$) 이 연산을 유한번 반복하면 모든 배열의 원소가 같아지는데 그 횟수의 최솟값을 구하는 문제이다.

 

배열은 앞에 있는 값을 뒤에 있는 값으로 대체하는 문제이므로 맨 뒤에 있는 값은 변할 수 없다. 결국 최종 배열은 맨 뒤에 있는 값만 가진 배열이 나올것이다. 그럼 뒤에서부터 같은 값이 얼마나 연속해서 있는지만 구하면 된다.

예를 들어 배열이 $[4,2,1,3,3]$이라고 하자.

마지막 값은 3이고 연속해서 2개가 있다.

이를 연산 처리하면 $[4,3,3,3,3]$이 된다.

같은 방법을 한번 더 사용하면 마지막 값이 연속해서 4개가 있으므로 $[3,3,3,3,3]$이 되어 2번만에 배열의 값을 같게 만들 수 있다.

 

C - And Matching

$n$은 2의 제곱수이고 $(0,1,...,n-1)$인 배열이 있을 때 이를 적당히 두개씩 짝지으면 $\frac{n}{2}$개의 집합이 만들어진다. $((a_1, b_1),(a_2,b_2), ..., (a_{\frac{n}{2}},b_{\frac{n}{2}}))$ 이때 $\sum_{i=1}^{\frac{n}{2}} a_i \& b_i = k$를 만들 수 있는지 묻는 문제이다.

 

내가 몰랐던 비트마스킹 기법을 사용한다. 우선 $2 = 10_{2}$이고 ~$2 = 01_{2}$인데 4자리 not연산을 하려면 $2 \oplus 15 = 1101_{(2)} $가 된다. 이를 일반화하면 $a$가 있고 $n$자리 not연산을 하려면 $a \oplus (2^n-1)$을 하면 된다. ($2^n-1 = 11...1_2$이기때문)

또한 $a \& $~$ a = 0$임은 자명하다. (근데 난 이것도 몰랐다. 이산수학을 들어야 하는 이유)

 

* Case 1) $k = 0$

$\sum_{x=0}^{\frac{n}{2}} x \&$~$x$로 구성하면 $0$이 나온다.

 

* Case 2) $0 \lt k \lt n-1$

$k \& (n-1) = k$ 이고 ~$k \& 0 = 0$이니까 남은 수 $0 < x < \frac{n}{2}, x \neq k, $~$k$에 대해 $(x, $~$x)$로 구성하면 $k$ 가 나온다.

 

* Case 3) $k = n-1$

이것도 2와 비슷하게 하면 되는데 $n-1 \& n-1$이 안되기 때문에 $n-1 \& n-2$를 하고 $1$을 찾자. 아무 홀수나 잡아도 되지만 가장 무난한 $n-3$을 고르면 $n-3 \& 1 = 1$이 나온다. 그 후 $(0, 2)$을 구성하고 남은 수들에 대해 $(x, $~$x)$로 짝지으면 된다.

여기서 $n=4$일때는 $n-3 \& 1$을 할 수 없으므로 해가 존재하지 않는다.

 

D - Range and Partition

배열이 주어지고 그 배열을 다음 조건에 맞게 정확히 $k$개의 부분배열을 만든다.

- 각 부분배열은 원래 배열에서 연속한 일부분이어야 한다.

- 원래 배열의 각 원소는 부분 배열중 하나에만 존재한다. (분할한다는 뜻인듯)

- 각 부분배열에서 $[x,y]$구간 안에 있는 원소 수가 구간 밖의 원소 수보다 크다.

이때 $y-x$를 최소화하는 방법을 구하는 것이 문제이다.

 

굉장히 기발한 방법으로 해결한다.

우선 구간 $[x,y]$를 정하고 새로운 배열 $b$를 정의하는데 $x \le a_i \le y$ 이면 $b_i=1$이고 그 외에는 $b_i=-1$로 정의한다. (이런 발상이 놀라웠다.)

그리고 $b$에 대한 부분합 $psum$을 구한다.

만약 전체 합 $psum_n \ge k$라면 조건에 만족하는 $k$개의 배열을 만들 수 있으므로 $1\lt x \lt k$에 대해 처음으로 $psum_i = x$일 때마다 분할하면 된다. 예를들어 $psum = [1,2,1,2,3,4], k=3$일 때 $[1], [2], [1,2,3,4]$로 분할하면 정답이 된다.

정답을 구하기 위해 구간 $[x,y]$를 구하는 과정은 다음과 같다.

$psum_n = \sum_{i=1}^n b_i = \sum_{i=1}^n {(-1+2 \cdot [x\le a_i \le y])} \ge k$

$\rightarrow \sum_{i=1}^n {[x\le a_i \le y]} \ge \lceil \frac{k+n}{2} \rceil $

등호일 때 최소가 되고 원래 배열을 정렬을 해서 $A$배열을 얻었을 때 $A_{i+\lceil \frac{k+n}{2} \rceil-1} - A_i$의 최솟값을 구하면 된다.

 

E - Paint the Middle

???

 

F - Flipping Range

???

 

코드포스는 배열을 적당히 조작하는걸 좋아하는것 같다.