Codeforces Round #780 div3

민트일 때 div3 잘 이용하면 blue 끝자락까지는 가능할 듯.

 

Dashboard - Codeforces Round #780 (Div. 3) - Codeforces

 

 

A. Vasya and Coins

 

Problem - A - Codeforces

 

1 burle의 가치를 가진 coin \( a \)개와 2 burle의 가치를 가진 코인 \( b \)개가 있다.

 

이 코인들로 표현할 수 없는 최소 burle을 구하시오.

 

 

너무 당연하지만 \( a \)가 0개라면 답은 1 (burle)이 될 것이다.

 

\( a \)가 1개 이상이라면 답은 \( a + 2 * b + 1 \)이 된다.

 

설명을 덧붙이자면, \( b \)개의 코인만으로 \( 2 * b \) 까지의 짝수를 만들 수 있다.

그리고 \( 2 * b + 1 \) 까지의 홀수는 여기에 1 burle을 하나 더 넣어서 만들 수 있다.

이후로는 1 bulre 코인 \( a \)개를 다 쓸 때까지 더해주면 된다. 그랬을 때 \( a + 2 * b \) 까지 표현 가능하므로 답은 \( a + 2 * b + 1 \)

 

 

 

B. Vlad and Candies

 

Problem - B - Codeforces

 

\( n \) 종류의 사탕이 각 종류마다 \( a_i \) ( \( i \leq n \) ) 개씩 있다.

 

Vlad는 한 번에 하나의 사탕을 먹으려 한다.

 

사탕을 순차적으로 다 먹으려고 할 때 같은 종류의 사탕을 연이어서 먹지 않으려고 한다.

 

그렇게 모든 사탕을 먹는 것이 가능한지 구하여라.

 

 

먼저 \( n = 1 \) 일 때, 사탕이 두 개 이상 있다면 불가능하다. 한 개라면 가능하다.

 

\( n > 1 \)일 때, 결국 가장 많은 특정 사탕과 두 번째로 많은 사탕의 수 (각각 \( a_i, a_j \) )를 비교하면 된다.

 

왜냐하면 그 사탕을 계속해서 먹으며 내려가면 다른 사탕들과 번갈아가면서 먹을 수 있기 때문이다.

 

따라서 \( a_i - a_j \leq 1 \) 이라면 가능하다.

 

그 외에는 불가능하다.

 

 

 

C. Get an Even String

 

Problem - C - Codeforces

 

문자열 \( a = a_1a_2...a_n \) 가 다음 조건을 만족한다면 even이라 부른다.

 

- \( n \)은 짝수

 

- 모든 홀수 \( i \) ( \( 1 \leq i \leq n - 1 \) ) 에 대해서, \( a_i = a_{i + 1} \)

 

문자열 \( a \) 가 주어졌을 때, even으로 만들기 위해 문자열에서 제거해야 하는 원소의 개수의 최솟값을 구하시오.

 

 

greedy 하게 원소를 지워도 답이 나오는 것을 알 수 있다.

 

\( a_i = a_j \), \( a_k = a_l \) 이외의 나머지는 모두 distinct 한 문자열이 있다고 하자.

 

만약 \( a_i ... a_k ... a_j ... a_l \) 이런 형태를 가진다고 했을 때, 이 문자열을 even으로 만들어주기 위해서는 결국 \( l - i + 1 \)개의 원소 중 두 개만 살리고 나머지는 지워야 한다.

 

따라서 \( a_i, a_j \) / \( a_k, a_l \) 중 어떤 쌍을 살리든 똑같은 개수의 원소를 없애야 한다.

 

\( a_i ... a_k ... a_l ... a_j \) 이런 꼴이라고 한다면, 당연히 \( a_k, a_l \)을 살리고 ( \( a_i ... a_{k - 1} \) 을 없애고 ) \( a_{l + 1} \) 부터 다시 순회하면 된다.

 

따라서 처음 원소부터 순회하며 이전에 같은 원소가 있었는지를 확인한 후 있었다면 이 외, 나머지 원소들을 다 지워주고, 이후로부터 다시 새로운 문자열로 생각하여 앞의 과정을 반복해주면 된다.

 

 

 

D. Maximum Product Strikes Back

 

Problem - D - Codeforces

 

\( n \) 길이의 array \( a \) 가 있다.

 

모든 \( i \) ( \( 1 \leq i \leq n \) ) 에 대해, \( -2 \leq a_i \leq 2 \) 를 만족한다.

 

배열의 앞에서 연속된 원소들을 지울 수 있고 뒤에서도 연속된 원소들을 지울 수 있다.

(하나도 안 지우는 것도 가능하다.)

 

앞에서와 뒤에서 몇 개의 원소들을 지워야 남은 원소들의 곱이 최대가 되는지 구하여라.

(단, 모든 원소들을 지웠을 때에는 1로 생각한다.)

 

 

결국 subarray 중 원소들의 곱이 최대가 되는 것을 구하면 된다.

 

이때, subarray 안에 0이 있으면 안 되고 (이 경우 다 지우는 게 더 크다) 음수가 홀수개 있으면 안 되며, 절댓값으로 2를 가지는 원소들이 많을수록 좋다.

 

따라서 먼저 0을 기준으로 array들을 잘라준다.

 

각 구간을 살피며 음수의 parity와 2의 개수를 확인한다.

 

만약 음수가 짝수개 있다면 그 구역 안에서의 곱이 최대가 되는 subarray는 그 구역 그 자체이다.

 

하지만 음수가 홀수개 있다면 왼쪽에서 원소들을 훑으며 음수인 원소를 찾아 그 이후부터 구역의 오른쪽까지를 확인한다.

 

오른쪽에서도 똑같은 작업을 해준다.

 

2의 개수를 비교하여 곱이 최대가 되는 subarray를 확인해준다.

 

parity나 2의 개수를 세는 것은 prefix sum으로 해결하면 된다.

 

 

 

E. Matrix and Shifts

 

Problem - E - Codeforces

 

\( n \) x \( n \) matrix A가 있다.

 

각 원소들은 0 또는 1이다.

 

matrix의 원소를 변형시킬 수 있다.

 

row나 column을 위/아래, 왼쪽/오른쪽으로 밀 수 있다. (1 -> n / n -> 1)

 

이러한 변형은 무한정 할 수 있다.

 

이후에 각 원소에 xor을 적용시켜 unitary matrix ( \( a_{ii} = 1 \) for \( 1 \leq i \leq n \), 나머지는 0) 로 만드려고 한다.

 

operation을 적절하게 하여 xor을 해야 하는 원소의 최소 개수를 구하시오.

 

 

왼쪽 위에서 오른쪽 아래로 내려가는 대각선에서 1의 개수가 최대가 되는 때를 찾으면 된다.

 

그다음에 (n - 1의 최대 개수 in 대각선) + (행렬 \( A \) 안에서의 모든 1의 개수 - 1의 최대 개수 in 대각선)을 구해주면 된다.

 

 

 

F. Promising String

 

Problem - F1 - Codeforces

 

Problem - F2 - Codeforces

 

같은 문제에 constraint만 다르다.

 

 

'+'와 '-'로 이루어진 문자열이 있다.

 

문자열 안에 '+'와 '-'의 개수가 같으면 balanced 되어 있다고 한다.

 

그리고 다음 operation을 0회 이상하여 balanced 문자열로 만들 수 있는 문자열을 promising 하다고 한다.

 

- 연이어 있는 마이너스 두 개 '--'를 플러스 하나 '+'로 바꿀 수 있다.

 

문자열이 주어졌을 때, promising substring의 개수를 구하시오.

 

 

F1 같은 경우 제한이 빡빡하지 않아서 그냥 완전 탐색 O( \( n^2 \) )을 하면 된다.

 

근데 F2에서는 이게 먹히지 않는다.

 

다른 방법을 알아봐야 한다.

 

 

관찰할 수 있는 사실은, minus 개수 - plus 개수가 3으로 나누어지면 문자열의 형태가 어떻게 되든 간에 promising 하다는 점이다.

(minus 개수가 plus 개수보다 더 많으면 무조건 연이어 있는 minus가 생길수밖에 없음)

 

minus 개수 - plus 개수를 \( cnt \)라고 한다면 \( (cnt_i - cnt_j)  % 3 = 0 \) 이고 \( cnt_i - cnt_j \geq 0 \)인 \( i, j \) ( \( i > j \) )의 쌍을 구하면 된다.

 

이러한 쌍을 어떻게 구하는가는 segment tree를 사용하면 된다.

 

아니면 배열으로 구할수도 있는데 gravekper님의 영상을 참조하자.