Codeforces Round #792 div2

 

https://codeforces.com/contest/1688

 

 

A. Cirno's Perfect Bitmasks Classroom

 

https://codeforces.com/contest/1688/problem/A

 

양의 정수 \( x \)가 주어졌을 때, \( x \text{ and } y > 0 \), \( x \text{ xor } y > 0 \) 를 만족하는 가장 작은 \( y \)를 구하시오.

 

 

먼저 and operation을 생각해보자.

 

\( x \text{ and } y > 0 \) 를 만족하기 위해 적어도 한 비트는 \( x \)와 \( y \) 가 동시에 켜져 있어야 한다.

 

가장 작은 \( y \)를 만들기 위해 \( x \)의 켜진 비트 중 가장 오른쪽 비트가 동시에 켜져 있다고 생각하자.

 

 

\( x \text{ xor } y > 0 \) 를 만족하기 위해 \( x \)의 꺼진 비트가 \( y \)에서는 켜져 있거나 \( x \)의 켜진 비트가 \( y \)에서는 꺼져있어야 한다.

 

가장 오른쪽에 있는 \( x \)의 켜진 비트는 위에서 이미 사용했으므로, \( y \)를 최소로 만들기 위해 가장 오른쪽에 있는 \( x \)의 꺼진 비트가 \( y \)에선 켜져 있다고 생각하자.

 

 

둘을 종합하면, \( x \)가 1인 경우 \( y \)는 3, 이 외에는 \( y = x & (-x) + 1 \)이라 할 수 있다.

 

 

 

B. Patchouli's Magical Talisman

 

https://codeforces.com/contest/1688/problem/B

 

\( n \)개의 양의 정수가 있다.

 

다음과 같은 operation을 할 수 있다.

 

- 두 수를 선택하여 없앤 후, 두 수의 합을 추가한다.

 

또는

 

- 수 하나를 선택하여 없앤 후, 2로 나눈 수를 추가한다.

 

모든 수를 홀수로 만드는 최소의 operation 횟수를 구하시오.

 

 

홀수 + 짝수 = 홀수이다.

 

따라서 n개의 수에 홀수가 하나라도 있으면 짝수의 개수가 답이 된다.

(홀수 + 짝수 = 홀수로 만들 수 있으므로)

 

 

모든 수가 짝수인 경우에는 어떨까.

 

수 하나를 홀수로 만들어서 위의 과정을 진행하는 것이 가장 적은 횟수임은 자명하다.

 

따라서 모든 수에 대해, 2로 나누었을 때 가장 빨리 홀수가 되는 수를 찾아 그 수를 홀수로 만든 후 남은 수들을 이 수와 더해 홀수로 만들어주면 된다.

 

 

 

C. Manipulating History

 

https://codeforces.com/contest/1688

 

길이 1의 string \( s \)가 주어진다.

 

이 string에 \( n \)번의 operation을 진행한다.

 

\( i \) 번째 operation은 다음과 같다.

 

- string \( s \)에서 non-empty substring \( t_{2i - 1} \)를 선택하여 non-empty string \( t_{2i} \)로 바꾼다.

( \( t_{2i - 1} \) \( \neq \) \( t_{2i} \) )

( \( t_{2i - 1} \)이 \( s \)에 2개 이상 등장하더라도 1개만 바꾼다.)

 

\( n \)번의 operation을 거쳐 최종적으로 얻은 string \( s \)와 순서가 뒤섞인 \( t_1, t_2, ..., t_{2n} \) 이 주어질 때, 최초의 \( s \)를 구하여라.

 

 

처음에는 어떤 방식으로 문제에 접근해야 하는지 감이 잡히지 않았다.

 

곰곰이 생각해보니 문자의 등장 횟수를 세는 방법으로 답을 구할 수 있겠다는 생각이 들었다.

 

 

어떤 문자가 \( s \)에 포함될 때와 다른 문자열로 바뀌는 경우를 모두 counting 하였을 때, 첫 번째 문자를 제외한 나머지 문자들은 포함될 때와 바뀌는 때가 쌍을 이룬다.

 

따라서 첫 번째 문자를 제외한 나머지 문자들의 등장 횟수는 짝수를 이룬다.

 

등장 횟수가 홀수인 문자가 답이 된다.

 

 

 

D. The Enchanted Forest

 

https://codeforces.com/contest/1688/problem/D

 

1부터 \( n \)까지의 좌표가 있다.

 

각 좌표에서 자라 있는 초기 버섯의 개수 \( a_1, a_2, ..., a_n \)이 주어진다.

 

다음과 같은 일이 순서대로 1초마다 일어난다.

 

- 좌표를 \( x \)에서 \( y \)로 바꾼다 ( \( | x - y | \leq 1 \)

 

- 좌표 \( y \)에 있는 모든 버섯을 수거한다.

 

- 모든 좌표에서 버섯이 하나 자란다.

 

\( k \)초 동안 모을 수 있는 버섯의 최대 개수를 구하시오.

 

시작 좌표는 아무 곳이나 가능하며, 0초부터 시작한다.

 

 

\( l = \min(k, n) \) 이라 하자.

 

답은 (길이 \( l \)인 consecutive sequence의 최대합) + ( (k - 1) + (k - 2) + ... + (k - l) ) 이 된다.

 

이는 자명한데, 안 가본 위치로 가는 선택지와 이미 갔던 위치로 가는 선택지 두 가지가 주어졌을 때, 안 가본 위치로 가는 선택지가 무조건 이득이다.

(가본 위치에서는 그동안 자랐던 버섯만 수거할 수 있지만 안 가본 위치에서는 그동안 자랐던 버섯 + 초기 버섯을 수거할 수 있기 때문)

 

또한, 마지막 방문 위치부터 거꾸로 생각을 해보자면, 마지막 방문 위치에서는 \( a_i + (k - 1) \)개의 버섯을, 그 전 방문 위치에서는 (중복되지 않는 위치를 가정할 시 ) \( a_j + (k - 2) \)개의 버섯을 얻을 수 있다.

 

이렇게 방문되지 않은 곳들을 방문하다, 또다시 좌표 \( i \)를 방문한다고 했을 때, 얻을 수 있는 버섯은 없다.

(초기 버섯은 이미 수거하였으며, 1초마다 자랐던 버섯의 최대 개수를 이미 수거하였으므로)

 

따라서 \( \min(k, n) \)번 이 과정을 진행하였을 때 가장 큰 값을 찾아주면 된다.