Codeforces Round #782 div2

Dashboard - Codeforces Round #782 (Div. 2) - Codeforces

 

 

A. Red Versus Blue

 

Problem - A - Codeforces

 

'R'과 'B'의 개수가 주어진다.

 

$cnt_R > cnt_B$ 이다.

 

연이어 나오는 문자의 최대 개수가 가장 작은 문자열을 만들어라.

 

( 예를 들어 $cnt_R = 2$, $cnt_B = 1$이라고 할 때, "RRB"는 연이어 나오는 문자의 최대 개수는 2, "RBR"은 1이다 )

 

 

$cnt_R > cnt_B$ 이므로 'B' 하나하나의 왼쪽 오른쪽에 'R'을 넣는 것이 유리할 것이다.

 

( R...R 'B' R...R 'B' R...R 이러한 방식으로 )

 

사이에 넣을 'R'의 개수를 최대한 분산하면 된다.

 

$\lceil \frac{cnt_R}{cnt_B + 1} \rceil 개나 \lfloor \frac{cnt_R}{cnt_B + 1} \rfloor 개를 적절히 사이사이에 배분한다.$

 

 

 

B. Bit Flipping

 

Problem - B - Codeforces

 

$n$ 길이의 '0'과 '1'로만 이루어진 문자열 $s$가 주어진다.

 

당신은 이 문자열에 정확히 $k$번 아래와 같은 operation을 진행하여야 한다.

 

- $i$ $1 \leq i \leq n$ 를 선택하여 문자열에서 $i$번째 비트를 제외한 나머지를 flip한다.

( flip이란 0 -> 1, 1 -> 0 으로 비트를 바꾸는 것을 의미한다. )

 

$k$번의 operation의 통해 구한 사전적으로 가장 큰 문자열과 operation을 위해 선택된 각각 index에 대한 횟수를 구하시오.

 

 

어떤 인덱스를 두 번 선택하는 것은 선택하지 않은 것과 같다는 것은 자명하다.

 

따라서 앞에서부터 순차적으로 operation을 적용하지 않을지, 한 번 적용할지 고려하다 만약 operation의 횟수가 남으면 마지막에 몰아주는 것이 좋다.

 

그리고 사전적으로 가장 큰 문자열을 구하는 것이기에 앞에서부터 1을 만드는 것이 좋을 것이다.

 

앞에서부터 순차적으로 1을 만들어보자.

 

$i$번째 문자를 고려한다고 할 때, parity를 1부터 $i - 1$번째 문자까지 적용한 operation 횟수의 parity라고 하자. ( even이라면 0, odd라면 1 )

 

인덱스 $i$에 대해 만약 남은 operation의 횟수가 짝수이고 $i$에 operation을 적용하지 않는다고 한다면 $s_i^parity$는 operation을 다 진행했을 때도 그대로이다.

 

따라서 $s_i^parity$가 1이라면 $i$를 선택하지 않으면 되고, 0이라면 한 번 $i$에 대해 operation을 적용하면 된다. ( 물론 이 경우 parity를 업데이트해주어야 한다. )

 

남은 operation의 횟수가 홀수일 때에도 비슷하다.

 

$i$에 operation을 쓰지 않는다고 한다면 결과적으로 $s_i^parity$가 flip 될 것이다.

 

따라서 $s_i^parity$가 0이라면 $i$를 선택하지 않고, 1이라면 한 번 operation을 적용해주면 된다.

 

이렇게 앞에서부터 1을 만들어가다가 operation을 다 쓰면 이후 문자들은 parity에 따라 update 해주면 된다.

 

operation의 횟수가 남았는데 마지막 인덱스까지 간다면 그만큼 마지막 인덱스에 operation을 해준다.

 

 

 

C. Line Empire

 

Problem - C - Codeforces

 

당신은 야심만만한 왕이다.

 

처음에는 제국의 수도가 0에 위치해있다.

 

$n$개의 정복되지 않은 도시 위치가 주어진다. ( $0 < x_1 < x_2 < ... < x_n$ )

 

당신은 다음과 같은 행동을 할 수 있다.

 

- 제국의 수도 위치가 $c_1$ 이고 다른 정복된 도시의 위치가 $c_2$일 때, \( a * |c_1 - c_2| \)의 비용으로 수도의 위치를 $c_1$에서 $c_2$로 바꿀 수 있다.

 

- 제국의 수도 위치가 $c_1$이고 아직 정복되지 않은 도시의 위치가 $c_2$일 때, $b * |c_1 - c_2|$의 비용으로 $c_2$에 위치한 도시를 정복할 수 있다.

( 단, $c_1$과 $c_2$ 사이의 모든 도시들은 정복된 상태여야 한다. )

 

주어진 $n$개의 도시를 정복하기 위한 최소 비용을 구하시오.

 

 

조금은 전형적인 greedy 문제이다.

 

현재의 수도 위치에서 다음 정복할 도시를 생각할 때, 현재의 수도에서 정복되지 않은 모든 도시들을 정복하기 위한 비용 vs 가능한 한 가장 오른쪽으로 수도를 옮긴 이후 정복되지 않은 모든 도시들을 정복하기 위한 비용을 비교하여 수도의 위치를 옮기는 것이 더 낫다면 옮기면 된다.

 

 

 

D. Reverse Sort Sum

 

Problem - D - Codeforces

 

$n$개의 원소를 가진 배열 $A$를 생각해보자.

( 모든 원소들은 0 또는 1이다. )

 

함수 $f(k, A)$를 다음과 같이 정의하자.

 

- $A$의 앞에서 $k$개의 원소들만 non-decreasing 순서로 정렬한 배열 $B_k$를 반환한다.

( 나머지는 그대로, ex) $f(2, [1, 0, 0, 1, 0] = [0, 1, 0, 1, 0]$

 

k를 1에서 $n$까지 넣어서 구한 함숫값 $B_1, B_2, ..., B_n$을 생각해보자.

 

그리고 배열 $C$는 $B_1, B_2, ..., B_n$들을 element-wise sum을 하여 구한 배열이다.

 

배열 $C$가 주어졌을 때, 배열 $A$를 구하시오.

 

 

먼저, $C$ 원소들을 모두 더하여 $n$으로 나누어 $A$에 있는 1의 개수($cnt$라 하자)를 구할 수 있다.

 

마지막 원소 ($C_n$) 부터 살펴보자.

 

만약 $C_n$이 n이라면 $A_n$의 값은 1이고, 그렇지 않다면 $A_n$의 값은 0이다.

 

이렇게 $A_n$ 값을 구한 후 $C$에서 $B_n$을 빼준다.

 

여기서 $B_n$은 뒤에서 $cnt$만큼의 원소들이 1, 나머지 원소들은 0인 형태를 띨 것이다.

 

이를 segment tree나 BIT, 또는 끝나는 위치를 배열에 저장하여 구현할 수 있다.

 

$A_n$이 1이라면 $cnt$에서 1을 빼주자.

 

그다음, $C_{n - 1}$에 대해서는 처음부터 원소의 개수가 $n - 1$이었던 것처럼 앞의 과정을 진행하면 된다.

 

앞으로 움직이며 모든 $A_i$의 값을 구해주자.

 

 

 

E. AND-MEX Walk

 

Problem - E - Codeforces