Codeforces Round #772 div2

A. Min or Sum

 

Problem - A - Codeforces

 

배열 A가 있다.

 

배열의 원소를 다음과 같은 operation으로 바꿀 수 있다.

 

For \(1 \leq i < j \leq n\), \(a_i\) to \(x\), \(a_j\) to \(y\) if \(a_i|a_j = x|y\)

 

operation을 몇 번이든 해도 상관없다고 하였을 때, 배열 A의 원소들의 합의 최솟값을 구하시오.

 

 

모든 원소들을 bitwise or 해준 값을 출력하면 된다.

 

 

B. Avoid Local Maximums

 

Problem - B - Codeforces

 

배열 A가 있다.

 

\(a_{i - 1} < a_i\) 이고 \(a_i > a_{i + 1}\) 라면 \(a_i\)를 local maximum이라고 한다.

 

그리고 \(a_i\) 를 아무 수로 바꾸는 operation이 있다.

 

A에서 local maximum을 없애는 최소한의 operation 수를 출력하여라.

 

첫 번째 원소와 마지막 원소는 local maximum이 될 수 없다.

 

 

배열을 차례대로 탐색하면서 local maximum을 찾는다.

 

찾은 local maximum의 index를 i라고 한다면 \(a_{i + 1}\)을 \(max(a_i, a_{i + 2})\)으로 바꿔준다.

 

\(i + 2\)이 배열의 범위를 벗어난다면 그냥 \(a_i\)로 바꿔준다.

 

 

C. Differential Sorting

 

Problem - C - Codeforces

 

배열 A가 있다.

 

for \(1 \leq x < y < z \leq n\), \(a_x\)를 \(a_y - a_z\)로 바꿔주는 operation이 있다.

 

operation을 사용하여 decreasing하는 부분 배열이 없도록 만든 후 operation 수와 indices를 출력하여라.

 

operation 횟수는 상관없다.

 

불가능한 경우 -1 출력.

 

 

첫 번째로, 주어진 배열이 non-decreasing한 배열이라면 바꾸어 줄 필요가 없다.

 

이 if문에 걸리지 않는 배열이라면 decreasing한 부분이 있다는 이야기이다.

 

\(a_{n - 1} > a_n\) 이라면 \(a_{n - 1}\)을 바꿀 수는 없으므로 불가능하다.

 

이 if문에 걸리지 않는다면 \(a_{n - 1} \leq a_n\) 이다.

 

그리고 \(a_n\)이 음수라도 불가능한데, 마지막 원소부터 차례대로 탐색을 했을 때 앞의 원소보다 더 큰 원소가 발견되었다고 하자. \((a_i > a_{i + 1})\)

 

그렇다면 \(i + 1\) 부터 마지막 원소까지는 non-decreasing한 배열이므로 마지막 원소가 가장 큰 수이다.

 

하지만 operation을 진행했을 때 더 큰 수를 만드므로 \(a_i\)를 조건에 맞도록 바꿀 수 없다.

 

따라서 \(a_{n - 1} \leq a_n\)이고 \(a_n \leq 0\)이라면 \(a_1\)부터 \(a_{n - 2}\)까지의 모든 원소들을 \(a_{n - 1}\)과 \(a_n\)을 이용하여 operation으로 수를 바꾸어주면 된다.

 

 

D. Infinite Set

 

Problem - D - Codeforces

 

\(f(x) = k\) if \(2^k \leq x < 2^{k + 1}\) 라고 정의하자.

 

그렇다면 \(f(2x + 1) = f(x) + 1\), \(f(4x) = f(x) + 2\) 라는 것을 쉽게 알 수 있다.

 

결국 dp문제로 바꿀 수 있다.

 

처음에 주어지는 배열에서 다른 원소로 만들어지는 중복되는 수같은 경우 배열을 오름차순으로 정렬한 뒤 다른 원소로

만들 수 있는지를 확인한다.

 

테스트를 통과한 수를 \(b_1, b_2, ..., b_k\)라 했을 때, \(a_i\)가 지금 탐색하는 수라고 한다면,

a_i가 0이 될 때까지 홀수라면 \(\frac{a_i - 1}{2}\)로, 4로 나누어진다면 \(frac{a_i}{4}\)로 만들며 \(b_1, .., b_k\)중에 있는지 찾아주고 저 조건에 부합하지 않는다면 거기서 끝낸다.

 

 

E. Cars

 

Problem - E - Codeforces

 

두 차간의 관계가 있다면 irrelevant거나 destined 둘 중 하나이다.

 

결국 두 차의 방향은 달라야 한다.

 

관계를 edge로 잇고 차들을 coloring 한다. (orientation을 구분)

 

그랬을 때, 인접한 두 차의 orientation이 같다면 불가능한 경우이다.

 

그런 다음, 차들의 orientation과 관계에 따라 위치의 대소 관계를 edge로 표현한다.

 

그리고 in degree가 0인 차들부터 시작하여 topological sorting을 진행해주며 위치를 정해준다.

 

 

F. Closest Pair

 

나중에 봐야지