요즘 빠른 3솔을 목표로 하고 있는데 이번은 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점이라도 얻었다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[알고리즘] Codeforces Round #784 (Div. 4) (0) | 2022.04.22 |
---|---|
[알고리즘] Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics) (0) | 2022.03.09 |
[알고리즘] 순열 사이클 분할 (0) | 2022.03.03 |
[알고리즘] Codeforces Round #772 (Div. 2) (0) | 2022.02.21 |
[알고리즘] Codeforces Round #771 (Div. 2) (0) | 2022.02.15 |