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