Educational Codeforces Round #126

Dashboard - Educational Codeforces Round 126 (Rated for Div. 2) - Codeforces

 

 

어렵다 어렵다 어렵다.

 

이 또한 쉬워지리라.

 

 

 

A. Array Balancing

 

Problem - A - Codeforces

 

\( a_1, a_2, ..., a_n \)과 \( b_1, b_2, ..., b_n \)이 주어진다.

 

다음과 같은 operation이 몇 번이든 가능하다.

 

- index \( i \) ( \( 1 \leq i \leq n \) ) 을 선택해서 \( a_i \)와 \( b_i \)를 스왑할 수 있다.

 

\( \sum_{i=1}^{n - 1} ( | a_i - a_{i + 1} | + | b_i - b_{i + 1} | ) \)의 최솟값을 구하여라.

 

 

결국 인접한 두 원소간의 차이를 더하는 것이다.

 

따라서 1부터 \( n - 1 \)까지 \( i \)를 iteration 하며 \( | a_i - a_{i + 1} | + | b_i - b_{i + 1} | \)와 \( | a_i - b_{i + 1} | + | b_i - a_{i + 1} | \) 둘 중 더 작은 것을 누적해서 합한다.

 

 

 

B. Getting Zero

 

Problem - B - Codeforces

 

정수 \( v \)가 있을 때 다음 operation을 할 수 있다.

 

- \( v = v + 1 \) mod 32768

 

또는

 

- \( v = ( 2 * v ) \) mod 32768

 

\( n \)개의 정수 \( a_1, a_2, ..., a_n \)이 있을 때 각 수를 0으로 만드는 operation의 최소 횟수를 구하여라.

 

 

나같은 경우 priority queue로 0부터 backtracking을 하여 각 수를 만들기 위한 최솟값을 구하여 저장하였다.

 

editorial이 훨씬 간단한데, \( 32768 = 2^{15} \) 이기 때문에 어떤 수이든 2를 최대 15번 곱해주면 0을 만들 수 있다.

 

2를 곱한 후 더하는 것은 최소 횟수를 구하는 것에 방해가 되기에 무조건 어떤 수를 더한 다음 곱해주어야 한다.

 

따라서 \( ((v + a) << b) = 0 \text{ mod 32768 } \) ( \( 0 \leq a \leq 15 \), \( 0 \leq b \leq 15 \) )을 만족시키는 \( a + b \)의 최솟값을 구해주면 된다.

 

 

 

C. Water the Trees

 

Problem - C - Codeforces

 

1부터 \( n \)까지 넘버링되어있는 나무들이 있다.

 

\( i \)-th 나무의 높이는 \( h_i \)이다.

 

홀수 날에 물을 주면 나무의 높이가 1 증가하고 짝수 날에 물을 주면 나무의 높이가 2 증가한다.

 

1일부터 시작하여 하루에 하나의 나무에만 물을 줄 수 있다.

 

모든 나무들의 높이를 같게 만들기 위한 최소 날은 언제인지 구하시오.

 

 

최종적으로 모든 나무들의 높이는 무엇이 될 수 있을까.

 

일단 기존에 있던 나무의 높이를 줄일 수 없기 때문에 주어진 나무 높이의 최댓값 이상이어야 할 것이다.

( \( h_{max} \) 라고 하자 )

 

\( h_{max} + 1 \)도 될 수 있을 것이다. 하지만 \( h_{max} + 2 \)부터는 불가능하다.

 

이 경우 물을 덜 줘서 \( h_{max} \)나 \( h_{max} + 1 \)을 만들 수 있기 때문이다.

 

따라서 \( h_{max} \)와 \( h_{max} + 1 \)인 경우를 살펴봐야 한다.

 

모든 나무들을 순회하며 최종 나무의 높이 ( \( h_{last} \) 라고 하자 )와의 차를 구해 높이 1을 무조건 줘야 하는 횟수와 2로 나눴을 때를 더해준다. ( 각각 one_cnt, two_cnt라 하자 )

 

필요한 일자는 max( one_cnt * 2 - 1, two_cnt * 2 )가 된다. 따라서 두 수의 차를 최대한 줄여보자.

 

diff = max( (two_cnt - one_cnt) / 3, 0 )을 구해 two_cnt에서 빼주고 one_cnt에 2 * diff만큼 더해준다.

 

그리고 일자를 계산해준다.

 

만약 two_cnt가 여력이 있다면 ( two_cnt > 1 의 경우 ), one_cnt += 2, two_cnt--를 해주고 일자를 구한다.

 

최종적으로 구한 일자들의 최솟값이 답이 된다.

 

 

 

D. Progressions Covering

 

Problem - D - Codeforces

 

\( n \) 개의 0으로 채워진 배열 \( A \)와 \( n \)개의 정수로 채워진 배열 \( B \)가 있다.

 

\( k \)가 주어졌을 때 다음의 operation을 할 수 있다.

 

- 배열 \( A \)에서 \( k \) 길이의 subsegment를 골라 첫 번째 원소부터 \( k \) 번째 원소까지 1, 2, ..., \( k \)를 더한다.

 

모든 \( i \) ( \( 1 \leq i \leq n \) )에 대해, \( B_i \leq A_i \)를 만족시키는 operation을 최소 횟수를 구하시오.

 

 

오른쪽에서 왼쪽으로 가며 \( B_i \)를 0 이하로 만들도록 operation을 진행해보자.

 

\( B_i \)에 대해서 sum은 \( B_{i + 1}, B_{i + 2}, ..., B_n \)에서 뺀 수의 합이라고 하고, \( cnt \)를 \( B_{i + 1}, B_{i + 2}, ..., B_n \)에서 진행한 operation의 횟수라고 하자.

 

그리고 \( \text{closed}_i \)는 이전에 적용하였던 operation이 끝나는 시점에서 앞에서 필요했던 operation의 개수라고 하자.

 

\( i \) 번째에 sum -= cnt, \( B_i \) -= sum, cnt -= \( \text{closed}_i \)를 해준 다음 \( B_i \)가 양수라면 minus = min( \( k \), \( i \) )를 계산해주고 operation을 진행할 횟수 need = \( B_i \) + minus - 1 / minus를 구해준다.

 

답에 need를 더해주고 sum += minus * need, cnt += need, \( i \) - minus 가 양수라면 \( closed_{i - \text{minus}} \) += need를 해준다.

 

 

과정이 조금 복잡한데 각각의 변수들이 어떠한 역할을 하는지 이해하기 위한 예를 하나 생각해보자.

 

\( k \)가 6이고 \( n \)이 8이다.

 

그리고 \( B_8 = 20 \)이라고 하자.

 

\( B_8 \)에서 뺄 수 있는 최댓값은 \( k \)인 6이다.

 

따라서 \( B_8 \)을 0 이하로 만들기 위해서는 operation을 4번 하여야 한다.

( \( 4 * k \) = 24 \( \geq B_7 = 20 \) )

 

따라서 cnt = 4, sum = 24, \( \text{closed}_{8 - 6} \) = 4가 된다.

 

이번에 진행했던 operation에 영향을 받아 \( B_7, B_6, ..., B_3 \)는 각각 20, 16, ..., 4를 빼야 한다.

 

이는 곧 sum에 cnt를 계속해서 뺀 수와 같다.

 

그리고 \( B_2 \)일 때 sum에 cnt를 빼고 \( \text{closed}_2 = 4 \)를 cnt에 빼준다.

(sum과 cnt는 모두 0이 된다)

 

이러한 과정으로 \( B_8 \)을 오른쪽 끝으로 한 operation의 영향을 없앨 수 있다.