오랜만에 contest에 다시 참여하였다. SCPC 2라운드에서의 경험을 맛보고, 학기를 끝낸 후에 그 동안 하지 못했던 PS를 다시 연습하는 시간을 가지려 contest에 참여하였다.
A. Wizard of Orz
풀이 보기
풀이
주어진 길이를 가진 수 중 가장 큰 숫자를 출력해야하므로, 가장 앞자리의 숫자는 $9$여야 한다.
뒤의 숫자는 앞과의 숫자와 차이가 1씩 떨어지면 된다. 요점은 어디에서 반전시킬 것인가이다.
만약 $n=3$이라면 정답은 $989$이다. 또 $n=4$라면 정답은 $9878$이 아닌 $9890$이다. 또 $n=5$라면 정답은 $98789$가 아닌 $98901$이다. 반전시키는 위치는 항상 2번째 자리인 것을 찾아내야 한다.
$n=1$이라면 $9$, $n=2$라면 $98$을 출력하고, 그 이후는 남은 자리수만큼 $0123456789$를 반복하여 출력하면 정답을 출력할 수 있다.
코드
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() {
#define MAX_INDEX (int)2e5
char str[MAX_INDEX + 1];
int t;
for (scanf("%d", &t); t; --t) {
int n;
scanf("%d", &n);
if (n == 1) {
printf("9\n");
}
else {
str[0] = '9', str[1] = '8';
int k = 9;
for (int j = 2; j < n; ++j) {
str[j] = k + '0';
if (++k > 9) {
k = 0;
}
}
str[n] = '\0';
printf("%s\n", str);
}
}
return 0;
}
B. Hills And Valleys
풀이 보기
Not solved
result : Wrong answer on pretest 3 ( pretest )
풀이
배열의 각 숫자에 대해 앞의 원소와의 관계를 이용하려하였다. 값이 아닌 증감만을 따로 기록하여 1개 ~ 3개 중 어떤 값까지 추가로 제거할 수 있는지를 판별하려 하였다.
반례가 있는 것인지, 아니면 이 방식으로 푸는 문제가 아닌지 확신이 들지 않는다. 나중에 따로 시간을 들여 풀어보아야겠다.
코드
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <stdio.h>
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) > (b)) ? (b) : (a))
typedef char boolean;
#define True 1
#define False 0
#define SAME 0
#define UP 1
#define DOWN 2
typedef struct Node {
int v;
int m;
} N;
#define NOT 0
#define HILL 1
#define VALLEY 2
int main() {
int t;
for (scanf("%d", &t); t; --t) {
#define MAX_INDEX (int)3e5
N arr[MAX_INDEX];
char hill[MAX_INDEX] = { NOT };
int n;
int result = 0;
int canBeErase = 1;
scanf("%d %d", &n, &arr[0].v);
arr[0].m = SAME;
for (int i = 1; i < n; ++i) {
int a;
scanf("%d", &a);
if (arr[i - 1].v < a) {
arr[i] = (N) { a, UP };
}
else if (arr[i - 1].v > a) {
arr[i] = (N) { a, DOWN };
}
else {
arr[i] = (N) { a, SAME };
}
}
for (int i = 1; i < n - 1; ++i) {
if (arr[i].m + arr[i + 1].m == 3) {
++result;
if (arr[i].m == UP) {
hill[i] = HILL;
}
else {
hill[i] = VALLEY;
}
}
else {
hill[i] = NOT;
}
}
if (result == 0 || (n == 4 && result == 2)) {
printf("0\n");
}
else {
for (int i = 2; i < n - 2; ++i) {
if (hill[i] == HILL && hill[i - 1] == VALLEY && hill[i + 1] == VALLEY ||
hill[i] == VALLEY && hill[i - 1] == HILL && hill[i + 1] == HILL) {
canBeErase = 3;
break;
}
else if (hill[i - 1] == HILL && hill[i] == VALLEY && hill[i + 1] == NOT && (arr[i + 1].v >= arr[i - 1].v || arr[i + 1].m == SAME) ||
hill[i - 1] == VALLEY && hill[i] == HILL && hill[i + 1] == NOT && (arr[i + 1].v <= arr[i - 1].v || arr[i + 1].m == SAME)) {
canBeErase = max(canBeErase, 2);
}
}
printf("%d\n", result - canBeErase);
}
}
return 0;
}
결과
| Contest | Start time | Rank | Solved | Rating change | New rating |
|---|---|---|---|---|---|
| #695 (Div. 2) | 2021/1/8 23:35 | 4762 | 1 | -9 | 1398 |
B번 문제의 정답을 오래 고민했지만 풀어내지 못했다. 1문제밖에 풀지 못해 rate가 많이 떨어질 것을 예상하였으나, 예상 외로 rank가 낮지 않았다. B번 문제에서 많이 떨어져 나간 것 같다. 그래도 rate는 1400점 이하로 떨어졌고, 다시 pupil에 진입하였다.
1문제밖에 풀지 못한 것도 아쉬웠고, specialist를 잃어버린 것도 아쉬웠다. 다음 contest에서는 specialist를 다시 얻기 위한 노력을 해야겠다.