3학년 1학기 끝나자마자의 contest 참여이다. 아마 결과는 처참하지 않을까 예상한다.
A. Arithmetic Array
풀이 보기
풀이
모든 원소의 합 $A$가 $k$와 같도록 조정하는 문제이다. 다만 추가할 수 있는 수가 음이 아닌 정수이므로, 만약 $A > k$라면 추가할 수 있는 숫자는 $0$뿐이다.
만약 $A = k$라면 수를 추가하지 않아도 평균을 1로 만들 수 있다.
만약 $A < k$라면 양수 하나만을 추가하여 평균을 1로 만들 수 있다. ( 이 때 추가하는 수는 아마도 $k - A + 1$일 것이다. )
만약 $A > k$라면 $A - k$만큼의 $0$이 추가로 필요하므로, 이것이 답이 된다.
코드
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
#include <stdio.h>
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
int sum = 0;
for (int i = 0; i < n; ++i) {
int a;
scanf("%d", &a);
sum += a;
}
if (sum == n) {
printf("0\n");
}
else if (sum < n) {
printf("1\n");
}
else {
printf("%d\n", sum - n);
}
}
return 0;
}
B. Bad Boy
풀이 보기
풀이
직관적인 문제이다. 가장 멀리 순회하기 위해서는 가장 겉부분을 돌면 된다는 간단한 원리를 눈치채면 풀 수 있는 문제이다.
고로 가장 큰 직사각형의 꼭짓점인 (1, 1)과 (n, m)을 방문하도록 지정하면 된다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int main() {
int t;
scanf("%d", &t);
while (t--) {
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
printf("%d %d %d %d\n", 1, 1, a, b);
}
return 0;
}
C. Challenging Cliffs
풀이 보기
풀이
$n$개의 산이 있는데, 이것을 이용하여 difficulty를 $n-1$로 만드는 것이 정답이다.
우선 주어진 조건에 따라 $|h_1 - h_n|$이 최소가 되는 두 개의 산을 찾아야 한다. 이것은 정렬된 산들을 이용하여 양옆의 산과 비교하면 쉽게 찾을 수 있다.
이후 그것을 양 옆에 배치하고, 정렬된 순서대로 산을 놓는다. 늘어놓은 모습을 앞에서 보게 된다면 번개 모양이 되도록 조정한다.
만약 정렬된 배열에서 양 끝점의 산의 index가 $a$, $a+1$이라고 한다면 아래와 같은 순서로 산을 선택한다. $[a+1, a+2, … n, 1, 2, …, a]$
이러면 $n$ -> $1$인 지점에서만 난이도가 증가하지 않으므로 난이도는 $n-1$이 되며 최대를 나타낸다.
코드
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
43
44
45
#include <stdio.h>
#define MAX_IDX (int)2e5
int cmp(int* a, int* b) {
return *a - *b;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int arr[MAX_IDX];
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", arr + i);
}
qsort(arr, n, sizeof(int), cmp);
if (n == 2) {
printf("%d %d\n", arr[0], arr[1]);
}
else {
int diff = arr[1] - arr[0];
int s1 = 0, s2 = 1;
for (int i = 1; i < n - 1; ++i) {
if (arr[i + 1] - arr[i] < diff) {
diff = arr[i + 1] - arr[i];
s1 = i, s2 = i + 1;
}
}
for (int i = s2; i < n; ++i) {
printf("%d ", arr[i]);
}
for (int i = 0; i <= s1; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
}
}
return 0;
}
결과
| Contest | Start time | Rank | Solved | Rating change | New rating |
|---|---|---|---|---|---|
| #726 (Div. 2) | 2021/6/18 23:35 | 5302 | 3 | -47 | 1492 |
3문제를 풀었는데, 누구든 당연하게 풀 수 있는 난이도의 문제들뿐이어서 점수가 상향평준화된 것 같다. D가 E1보다 어려워서 이 부분에서 시간을 더 많이 잡아먹은 것이 패인인 것 같다.