Codeforces Round #781 div2

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

 

 

A. GCD vs LCM

 

Problem - A - Codeforces

 

 

양의 정수 \( n \) ( \( n \geq 4 \) ) 이 주어졌을 때, 다음을 만족하는 양의 정수 \( a, b, c, d \)를 구하라.

 

- \( a + b + c + d = n \)

 

- gcd( \( a, b \) ) = lcm( \( c, d \) )

 

 

\( b, c, d \)를 1로, \( a \)를 \( n - 3 \) 으로 두면 조건을 만족한다.

 

 

 

B.  Array Cloning Technique

 

Problem - B - Codeforces

 

 

\( n \) 길이의 array \( a \)가 주어진다.

 

초기에는 주어진 array만 존재한다.

 

두 가지의 operation을 할 수 있다.

 

- array 하나를 정해서 하나의 복사본 array를 만든다.

 

- 두 array에서 각각 원소 하나를 정해 swap한다.

 

한 array의 모든 원소들을 같게 만드려고 할 때, operation의 최소 횟수를 구하시오.

 

 

처음 주어진 array에서 가장 많이 나오는 element의 개수를 구한다.

(가장 많이 나온 원소 e의 개수를 cnt라고 하자)

 

그런 다음 array를 복사하여 복사본에서의 e와 원래의 array에서의 e가 아닌 원소를 swap 해준다.

(min(n - cnt, cnt) 만큼 swap)

 

만약 초기 array의 모든 원소가 e라면 종료한다.

 

그렇지 않다면 초기 array에는 e가 2 * cnt만큼 있다.

 

다시 복사해서 swap 하고 e가 아닌 원소들이 사라질 때까지 반복한다.

 

 

 

C. Tree Infection

 

Problem - C - Codeforces

 

 

1을 root로 하는 \( n \)개의 vertex를 가진 tree가 주어진다.

 

초기에는 모든 vertex들이 건강하다.

 

1초마다 두 operation을 동시에 진행할 수 있다.

 

- vertex v를 감염시킨다.

 

- vertex v에 대해 v의 자손 중 적어도 하나가 감염되었을 때, 다른 자손을 감염시킬 수 있다.

 

모든 vertex들을 감염시키기 위한 가장 빠른 시간을 구하여라.

 

 

먼저, 모든 vertex들의 in-degree를 구한다.

 

그리고 in-degree가 0이 아닌 vertex들의 개수를 구한다. (cnt라고 하자)

 

이때 cnt + 1초 이상의 시간이 무조건 필요하다는 것은 자명하다.

(in-degree가 0이 아니라는 뜻은 그 vertex가 leaf 노드가 아니라는 뜻이다. 따라서 자손들 중 하나를 무조건 감염시킬 시간이 필요하다. +1을 해주는 이유는 root를 감염시키기 위해)

 

다음으로 in-degree들을 큰 순서대로 정렬한다.

 

in-degree가 큰 순서대로 그 vertex의 자손을 먼저 감염시키는 것이 가장 최적일 것이다.

 

따라서 in-degree가 큰 것부터 작은 것 순으로 감염시켰을 때 cnt + 1초가 지나도 건강한 채로 남아있는 node의 개수를 각각 구한다.

 

남아있는 건강한 node들을 감염시키기 위해 필요한 시간을 parametric search로 구한다.

 

시간 t로 남아있는 node들을 감염시킬 수 있는지를 확인하는 방법은 다음과 같다.

 

- 남아있는 node들의 개수를 순회하며 t와 비교한다.

 

- 만약 t보다 작거나 같다면 t 시간이 지났을 때 모두 감염된다.

 

- 만약 t보다 크다면 차를 누적해서 더한다.

 

- 누적합이 t보다 작거나 같다면 가능하다.

(왜냐하면 t초동안 한 노드를 정해 감염시킬 수 있으므로)

 

- 그렇지 않다면 불가능하다.

 

 

 

D. GCD Guess

 

Problem - D - Codeforces

 

 

당신은 다음과 같은 query를 보낼 수 있다.

 

- "? a b" ( \( 1 \leq a, b \leq 2 * 10^9, a \neq b \) )

 

query의 응답으로는 gcd( \( x + a, x + b \) ) 값을 받는다.

 

최대 30번의 query를 보내 양의 정수 \( 1 \leq x \leq 10^9 \) 를 추측하여라.

 

 

먼저, \( a \)와 \( b \)의 대소 관계는 그리 중요한 것이 아니므로 \( a < b \)라 생각하자.

 

그랬을 때, gcd( \( x + a, x + b \) )를 gcd( \( b - a, x + a \) )로 바꿀 수 있다.

 

 

\( x \)를 이진수로 나타냈을 때의 오른쪽 \( k \)개 bit들의 값을 \( r \)이라고 하자.

 

당연하게도 \( x - r \)을 이진수로 나타냈을 때, 오른쪽 k bit들은 0이다.

 

여기서 \( 2^k \)를 더해준 \( x - r + 2^k \)와 \( 2^{k + 1} \)의 gcd가 \( 2^{k + 1} \)이라면 \( x \)의 \( k + 1 \)번째 bit는 1이다. 그렇지 않다면 0이다. 이를 \( r \)에 반영해준다.

 

0부터 29까지 \( k \)에 대입해  이 과정을 반복하면 된다.

 

 

 

E. MinimizOR

 

Problem - E - Codeforces

 

 

\( n \) 길이의 array \( A \)가 주어진다.

 

\( q \)개의 구간 \( l, r \) ( \( 1 \leq l < r \leq n \) ) 이 주어지면 구간 안의 모든 원소 \( a_i, a_j \) ( \( i \neq j \) )에 대해 \( a_i | a_j \)의 최소값을 구하시오.

 

 

모든 원소들이 \( 2^k \) 보다 작다면, 구간 안에서 가장 작은 \( k + 1 \)개의 원소들의 모든 쌍들을 bitwise or 계산하여 최솟값을 구하면 된다고 한다.

 

귀납법으로 증명 가능하다.

 

먼저 \( k = 1 \)일 때는 자명하다.

 

\( k \)일 때 답을 구하기 위해 가장 작은 \( k + 1 \)개만큼의 원소들이 필요하다고 하자.

 

이때, \( k + 1 \)이라면 답을 구하기 위해 \( k + 2 \)개만큼의 원소들이 필요하다는 것을 보이면 된다.

 

1. 모든 원소들이 \( 2^{k + 1} \)보다 작을 때, 모든 원소들의 \( k + 1 \)번째 bit가 1이라면 답의 \( k + 1 \)번째 bit가 무조건 1이 되므로 모든 원소들의 \( k + 1 \)번째 bit를 잘라낸 \( k \)개의 bit만 생각하면 된다.

 

이는 곧 모든 원소들이 \( 2^k \)보다 작다는 뜻이다. 따라서 \( k + 1 \)개만큼의 원소들이 필요하다.

 

2. 모든 원소들이 \( 2^{k + 1} \)보다 작을 때, \( k + 1 \)번째 bit이 0인 원소들이 2개 이상이라고 하자.

 

이때, 답의 \( k + 1 \)번째 bit은 무조건 0이 되어야 한다.

 

따라서 \( k + 1 \)번째 bit이 0인 원소들만 가져와서 \( k + 1 \)번째 bit을 제외한 \( k \)개의 bit만 생각해준다.

 

이는 곧 이 원소들이 \( 2^k \)보다 작다는 뜻이다. 따라서 \( k + 1 \)개만큼의 원소들이 필요하다.

 

3. 모든 원소들이 \( 2^{k + 1} \)보다 작을 때, \( k + 1 \)번째 bit이 0인 원소가 하나만 존재한다고 하자.

 

그렇다면 일단 그 특정 원소들을 제외한 나머지를 생각하였을 때, 조건이 1과 같아진다.

 

따라서 \( k + 1 \)개만큼을 원소들로 계산해주면 된다.

 

여기다 제외했었던 \( k + 1 \)번째 bit이 0인 원소까지 포함하여 계산해준다.

 

따라서 가장 작은 \( k + 2 \)개의 원소들로만 계산해주면 된다.

 

 

문제에서 주어진 조건으로 인해 모든 원소들이 \( 2^{30} \)보다 작다는 것을 확인할 수 있다.

 

따라서 min(구간의 길이, 31) 개만큼의 최솟값을 구간에서 뽑아주면 된다.

 

구간의 최소값을 관리하는 것은 segment tree로 구현해준다.

 

그리고 구간에서 최소값을 하나씩 뽑아낼 때마다 그 원소를 infinity로 update 해준다.

 

필요한 최솟값들을 모두 뽑아낸 다음에는 서로 bitwise or 해보며 가장 작은 값을 가져오면 된다.

 

이후 infinity로 update 한 원소들은 다시 원래대로 되돌려준다.