[알고리즘] Codeforces Round #774 (Div. 2)

요즘 빠른 3솔을 목표로 하고 있는데 이번은 C에서 너무 막혔다.

C의 상태가..?

 

A - Square Counting [Solved!]

$n+1$개의 수 $a_1, a_2, ..., a_n, a_{n+1}$이 주어질 때 $0\le a_i < n$이거나 $a_i = n^2$을 만족한다. 그리고 $\sum_{i=1}^{n+1} a_i = s$를 만족하는 $a_i = n^2$의 개수를 구하는 문제이다.

 

$s$에 $n^2$을 최대한 많이 넣으면 된다.

이를 구하려면 $\lfloor \frac{s}{n^2} \rfloor$을 계산하면 된다.

 

B - Quality vs Quantity [Solved!]

수열 $a_1, a_2, \dots, a_n$이 주어지고 각 수를 빨간색, 파란색, 색칠하지 않음 중 하나의 상태로 만들 때 빨간 수의 합 > 파란수의 합 이면서 빨간수의 개수 < 파란수의 개수 로 만들 수 있는 방법이 있는지 출력하는 문제이다.

     

우선 수열을 정렬한다.

* Case 1) $n$이 짝수

뒤에서부터 $\lfloor \frac{n}{2}-1 \rfloor$개를 빨간색으로, 앞에서부터 $\lfloor \frac{n}{2} \rfloor$개를 파란색으로 칠하면 답이 된다.

 

* Case 2) $n$이 홀수

뒤에서부터 $\lfloor \frac{n}{2} \rfloor$개를 빨간색으로, 앞에서부터 $\lfloor \frac{n}{2}+1 \rfloor$개를 파란색으로 칠하면 답이 된다.

 

이렇게 하면 파란색이 많다는게 보장되고 빨간색에 최대한 큰 값들이 들어갈 것이다.

이제 각 색깔로 색칠된 수들의 합을 비교하여 가능여부를 출력하면 된다.

 

C - Factorials and Powers of Two [Solved!]

2의 제곱수나 어떤 수의 팩토리얼을 powerful하다고 하자. 수가 주어지면 서로 다른 powerful한 수들의 합으로 나타낼 수 있는지 있다면 사용한 수의 최소개수를 출력하는 문제이다.

 

우선 주어진 수를 $n$이라고 하면 이는 언제나 대응되는 2진수가 있기 때문에 powerful한 수들의 합으로 나타낼수 있다는 것이 보장된다. (-1을 출력할 일이 없음)

이 경우 2진수로 변환한 후 1의 개수를 합해주면 된다.

$1\le n \le 10^{12}$이므로 범위에 해당하는 팩토리얼을 전처리해준다.

개수가 14개 나오는데 1, 2는 2의 제곱수와 겹치므로 빼주면 12개가 나온다.

이제 각 팩토리얼 수를 $f_1, f_2, \dots, f_{12}$라고 하면 각 수를 뺐을 때와 빼지 않았을 때를 모두 구한다.

모두 구하면 $n, n-f_1, n-f_2, \dots, n-f_{12}, n-f_1-f_2, n-f_1-f_3, \dots, n-f_1-f_{12}, \dots$ 같은 모양이 나올것이다.

전체 개수는 $2^{12} = 4096$개가 나온다.

각 수를 이진수로 바꿔 1의 개수를 합하고 뺀 팩토리얼 개수를 더한 뒤 최솟값을 구하면 정답이 된다.

 

C번문제를 풀며 맞왜틀을 수십번은 외쳤고 7번정도 제출 뒤 마지막에 재귀함수에서 base condition이 잘못됐다는걸 발견해서 400점이라도 얻었다.