CodeTON #1

부활!

 

vim을 써서 그런지 문제 푸는 속도가 생각보다 빠르다.

 

근데 이런식으로 가다가는 자칫 기본기가 부족해서 해답이 전혀 떠오르지 않는 문제를 만났을 때 죽 쑬 수도 있을 것 같다.

 

 

Dashboard - CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

 

 

A. Good Pairs

 

Problem - A - Codeforces

 

양의 정수 array \( a_1 \), \( a_2 \), ..., \( a_n \)이 있을 때, 다음의 조건을 만족하는 쌍 ( \( i \), \( j \) ) ( 1 \( \leq \) \( i,j \) \( \leq \) \( n \) )을 good pair라고 한다. 

 

For all \( 1 \leq k \leq n \)

$$ |a_i - a_k| + |a_k - a_j| = |a_i - a_j| $$

 

가능한 good pair 하나를 찾아라. \( i \)와 \( j \)는 같을수도 있다.

 

 

array를 정렬한 후, 가장 앞의 원소와 가장 뒤의 원소를 뽑으면 된다.

 

 

 

B. Subtract Operation

 

Problem - B - Codeforces

 

\( n \)개의 정수 list가 있다. 다음과 같은 operation을 원소가 하나가 남을 때까지 진행한다.

 

- list에서 원소 \( x \)를 뽑아 list에서 제거하고 남은 모든 원소들로부터 \( x \)를 뺀다.

 

수 \( k > 0 \) 가 주어졌을 때, 마지막 남은 원소의 값이 될 수 있는지를 구하시오.

 

 

첫 번째 원소를 골라서 operation 해보자. list의 형태는 다음과 같다.

 

$$ a_2 - a_1, a_3 - a_1,..., a_n - a_1 $$

 

여기서 다시 첫 번째 원소를 골라서 operation을 하자.

 

$$ a_3 - a_2, ..., a_n - a_2 $$

 

관찰을 통해 결국 마지막 남는 원소에서 operation을 위해 마지막으로 고른 수를 뺀 값이 남는 것을 알 수 있다.

 

따라서 \( a_i \)에 대해 \( a_i - a_j = k \)를 만족하는 \( a_j \)를 찾으면 된다.

 

sorting 후 이분탐색을 하거나 map을 사용해서 풀 수 있다.

 

 

 

C.  Make Equal With Mod

 

Problem - C - Codeforces

 

\( n \)개의 음의 정수가 아닌 정수들의 array 가 있다. 정수 \( x \geq 2 \)를 골라서 모든 element들에 모듈러 연산을 할 수 있다. 이 연산을 0번 이상 하였을 때 남는 수들을 다 같은 수로 만들 수 있는가.

 

 

만약 array의 원소들이 2 이상이거나 0이라면 큰 수부터 모듈러 연산을 하여 모두 0으로 만들 수 있다.

 

그 말은 즉슨 1이 없으면 모든 수들을 0으로 만들 수 있다는 뜻이다.

 

그렇다면 1이 있는 경우는 어떨까.

 

1을 바꿀 수 없으므로 모든 수들을 1로 만들어 줘야 한다.

 

마찬가지로 큰 수부터 \( mod (a_i - 1) \)을 해서 1로 만들 수 있다.

 

하지만 \( a_i - 1 \)이 array에 있어버리면 그 원소는 0이 된다.

 

따라서 array에 1이 있는 경우, 원소들의 간격이 2 이상이어야 한다.

 

 

 

D. K-good

 

Problem - D - Codeforces

 

만일 양의 정수 \( k \)에 대해 양의 정수 \( n \)이  \( k \)개의 양의 정수의 합으로 이루어지고 그 \( k \)개의 수들이 \( k \)로 나눈 나머지가 distinct할 때 \( n \)을 \( k \)-해ㅐㅇ dlfkrh gksek.

 

\( n \)이 주어졌을 때, \( k \)-good을 만족하는 \( k \)를 구하시오.

 

 

\( k \)개의 양의 정수들을 \( k \)로 모듈러 연산을 했을 때, 모두 distinct 해야 하므로 \( n \)은 다음과 같이 표현할 수 있다.

 

$$ n \mod k = 0 + 1 + 2 +... + k - 1 \mod k$$

 

즉,

 

$$ n = \frac{k(k + 1)}{2} + k*a $$

 

이라는 식이 나온다.

 

식을 조금 풀어보자.

 

$$ 2n = k^2 + k + 2ak $$

$$ k^2 + (2a + 1)k - 2n = 0 $$

 

\( n \)의 약수 \( \alpha \), \( \beta \)에 대해 \( n = \alpha\beta \) 로 표현할 수 있을 때, 식을 다음과 같이 바꿀 수 있다.

 

$$ (k - \alpha)(k + 2\beta) = 0 $$

 

또는

 

$$ (k - 2\alpha)(k + \beta) = 0 $$

 

\( k \)는 양의 정수이므로 \( k = \alpha \)거나 \( k = 2\alpha \)이다.

 

여기서 \( a \)는 0 이상의 정수이다.

 

따라서 \( 2\beta - \alpha \) 혹은 \( \beta - 2\alpha \)는 1 이상의 홀수가 되어야 한다.

 

이 수들이 홀수가 되는 것이 중요한 포인트다.

 

두 수의 차가 홀수가 되기 위해 하나는 홀수 하나는 짝수가 되어야 한다.

 

근데 2가 붙어있다.

 

따라서 \( n \)이 2로 나누어지는 만큼 \( \beta \)나 \( \alpha \)에 몰아주어야 한다.

 

2를 몰아준 수를 \( \beta \), 나머지를 \( \alpha \)라고 하자. (당연히 \( \beta \)는 \( 2^i \) 꼴, \( \alpha \)는 \( \frac{n}{\beta} \))

 

그랬을 때, \( 2\beta - \alpha \)가 1 이상이고 \( \alpha \geq 2 \)라면 \( \alpha \)가 답이 된다.

( \( k \geq 2 \) 이므로)

 

아니면 2를 \( \alpha \)에 몰아준다면 \( \beta - 2\alpha \)가 1 이상이면 \( 2\alpha \)가 답이 된다.

( \( 2\alpha \)는 무조건 2 이상이므로 체크를 해줄 필요 없음)

 

그 외는 불가능한 경우이다.

 

\( \alpha \)와 \( \beta \)를 다르게 설정하여 다른 \( k \)를 구할 수 있지 않느냐는 의문이 들 수 있다.

 

예를 들어 한쪽에 2를 몰아준 후 홀수 약수들을 더 넘겨준다던지.

 

하지만 이 방법이 음 가장 널널하게 조건을 만족시키는 방법이다. (글로 적기가 힘들다.)

 

 

 

E. Equal Tree Sums

 

Problem - E - Codeforces