조금만 있으면 Expert에 진입할 수 있다. 이번 contest에서 20점만 얻어도 1600점에 도달하여 파란색 닉네임을 달 수 있다.
기합 넣고 가자ㅏㅏㅏㅏ~
A. Pretty Permutations
풀이 보기
풀이
예제만 봤다가 한번 틀린 문제이다.
모든 원소를 한 칸씩만 미루는 것이 정답이 아니다. 만약 $n$개의 원소를 한칸만 미루는 것은 거리가 $2n-2$가 된다. 이것이 최소가 아니었다.
정답은 2개씩 묶어 서로 위치를 바꾸는 방법이다. 만약 원소의 개수가 홀수라면 마지막 남는 3개의 원소는 서로 한칸씩 밀어 모든 원소의 거리가 1이 되도록 조정할 수 있는 방법이 있다. 이 방법을 이용하면 거리가 $n$인 방법으로 모든 원소의 자리를 바꿀 수 있다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
int a = n >> 1;
if ((n & 1) > 0) {
for (int i = 1; i < a; ++i) {
printf("%d %d ", i << 1, (i << 1) - 1);
}
printf("%d %d %d\n", n - 1, n, n - 2);
}
else {
for (int i = 1; i <= a; ++i) {
printf("%d %d ", i << 1, (i << 1) - 1);
}
printf("\n");
}
}
return 0;
}
B. Pleasant Pairs
풀이 보기
풀이
모든 원소에 대해 검사하면 시간이 부족한 문제이다. 이 문제는 내가 온전히 풀었다고는 말하기 힘든 문제이다.
두 원소의 곱이 두 index의 합과 같음을 찾는 문제인데, 탐색 횟수를 줄이는 방법으로 앞의 원소의 값을 이용했다. 원소는 각각 자연수로 이루어져 있으므로, 두 index의 합 $i+j$는 원소 $a_i$의 배수여야한다. 이 점을 이용하여 개수를 모두 세는 브루트포스 방법으로 통과가 가능했다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#define MAX_IDX (int)1e5
long long arr[MAX_IDX + 1];
long long n;
int main() {
int t;
scanf("%d", &t);
while (t--) {
long long result = 0;
scanf("%d", &n);
for (long long i = 1; i <= n; ++i) {
scanf("%lld", arr + i);
}
for (long long i = 1; i <= n; ++i) {
long long a = arr[i];
long long temp = (2 * i) % a;
for (long long b = i - temp + a; b <= n; b += a) {
result += (a * arr[b] == i + b);
}
}
printf("%lld\n", result);
}
return 0;
}
C. Great Graphs
풀이 보기
풀이
음수 사이클을 만들지 않는 선에서 그래프가 가질 수 있는 cost 합의 최소를 찾는 문제이다.
우선 양수인 edge부터 생각해보자. cost의 최소가 되도록 해야하므로 양수인 edge는 가장 적게 사용하는 것이 좋다. 그 때의 edge의 합은 distance가 가장 큰 원소까지의 cost가 될 것이다. 예를 들어 배열이 $[0, 2, 4, 8, 11]$이라고 하면 아래의 양수 cost를 사용하는 것이 최소이다. 배열은 정렬하여 순서를 맞추고 edge를 추가해나가는 것이 좋다.
- $0$ -> $2$까지의 cost $2$
- $2$ -> $4$까지의 cost $2$
- $4$ -> $8$까지의 cost $4$
- $8$ -> $11$까지의 cost $3$
- 위의 모든 cost의 합 = $11$ ( distance가 가장 큰 원소와 값이 같다 )
이제 가능한 모든 음수 edge를 추가하면 된다. 우선 양수 edge의 반대로 모든 edge에 같은 양의 음수 edge를 설치할 수 있다. 따라서 위의 양수 edge를 모두 상쇄하는 음수 edge를 그릴 수 있다. 고로 정답이 양수가 나오는 경우는 존재하지 않는다.
또한 각 원소들을 거미줄 형태로 그릴 때 edge를 추가할 수 있는지 검사한다. 규칙을 찾으면 알겠지만, 아래와 같은 규칙을 가지게 된다.
- 1번 정점 ( 시작지점 ) 은 어떤 것과도 추가로 연결할 수 없다.
- 2번 정점은 1번 정점과 연결할 수 있다. 물론 이것은 위에서 언급한 양수 edge 상쇄에 사용되므로 고려하지 않아도 된다.
- 3번 정점은 1번 정점에 추가적으로 음수 edge를 그릴 수 있다. 이 때 사이클을 만들지 않는 수준에서 만들 수 있는 cost의 최댓값은 $a_3 - a_1$이다. ( 2번으로 연결하는 edge는 양수와의 edge의 상쇄에 사용한다. )
- n번 정점은 1번 정점부터 n-2번 정점까지 추가적으로 음수 edge를 그릴 수 있다. 이 때의 추가로 제거 가능한 cost는 $\sum{a_n - a_i}$이다. 이것을 공식화하면 $(n-2) \times{a_n} - \sum_{i=1}^{n-2}{a_i}$이다.
따라서 위의 수식을 모든 정점에 대해 더해주면 답을 얻을 수 있다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#define MAX_IDX (int)1e5
long long arr[MAX_IDX];
int n;
#define max(a, b) (((a) > (b)) ? (a) : (b))
int cmp(long long* a, long long* b) {
if (*a > *b) {
return 1;
}
else if (*a == *b) {
return 0;
}
else {
return -1;
}
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
long long ret = 0;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%lld", arr + i);
}
qsort(arr, n, sizeof(long long), cmp);
long long sum = 0;
for (int i = 2; i < n; ++i) {
ret -= (arr[i] * (i - 1) - sum);
sum += arr[i - 1];
}
printf("%lld\n", ret);
}
return 0;
}
결과
| Contest | Start time | Rank | Solved | Rating change | New rating |
|---|---|---|---|---|---|
| #728 (Div. 2) | 2021/6/26 00:35 | 921 | 3 | +47 | 1628 |
C번 문제 이후로는 참가자 대부분이 문제를 풀지 못했다. contest 종료 때는 D번 문제를 푼 사람이 7명뿐이었고, E번 이후로는 푼 사람이 없을 정도로 문제가 오버밸런스였다. C번 문제까지 얼마나 빠르게 문제를 풀었느냐가 등수를 가른 요소가 되었다.
1600점을 돌파했다! Expert 단계에 진입했고, 파란색 닉네임을 획득했다. 유지하면서 버티는 것을 우선 목표로 잡아야겠다.