2달만의 contest 참여이다. 시간이 이렇게 안날줄은 몰랐지..
오랜만에 친구가 같이 참여해보자 해서 참가한 contest이다. ps를 너무 많이 쉬어서 실력이 꽤 떨어졌을 것이라 생각되어서 난이도를 낮춰 Div. 3에 참가하였다.
A. Strange Table
풀이 보기
풀이
직관적이고 쉬운 문제이다.
우선 예시로 각 지점의 좌표는 (n, m)으로 나타낼 수 있다.
| 0, 0 | 0, 1 | 0, 2 | 0, 3 | 0, 4 |
| 1, 0 | 1, 1 | 1, 2 | 1, 3 | 1, 4 |
| 2, 0 | 2, 1 | 2, 2 | 2, 3 | 2, 4 |
이 때 구하는 $x$의 값은 $m\times{column}+n$으로 나타낼 수 있다.
마찬가지로, 문제에서 구하려는 “by rows”에서는 $x$의 값을 $n\times{row}+m$으로 나타낼 수 있다.
따라서 n과 m만 구하면 원하는 정답을 찾아낼 수 있다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
int main() {
int t;
scanf("%d", &t);
while (t--) {
long long n, m, x;
scanf("%lld %lld %lld", &n, &m, &x);
--x;
long long a = x / n, b = x % n;
printf("%lld\n", b * m + a + 1);
}
return 0;
}
B. Partial Replacement
풀이 보기
풀이
문제에서 주어진 조건 중 가장 유심히 봐야 할 줄이 있다.
“It is guaranteed that the distance between any two neighboring ‘*’ characters does not exceed $k$.”
이 문장의 의미를 해석하면, 어떻게든 뛰더라도 길이 끊기지 않고 도달할 방법이 있다는 것이다.
그렇다면 뛰어야 할 상황에서 가능한 선택지가 여러개 있다면 가장 멀리 뛰는 것이 뛰는 횟수를 줄일 수 있는 방법일 것이다.
그렇다. 이 문제는 최대한 멀리 뛰는 것을 반복하여 그리디 알고리즘을 사용한다.
코드
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
#include <stdio.h>
#define MAX_LEN 50
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, k;
scanf("%d %d", &n, &k);
char str[MAX_LEN + 1];
scanf("%s", str);
// find first *
int start = 0, end = n - 1;
for (; start < n && str[start] == '.'; ++start);
for (; end >= start && str[end] == '.'; --end);
if (start == end) {
printf("1\n");
}
else {
int a = 1;
while (start < end) {
int i;
for (i = start + k; start < i && str[i] == '.'; --i);
start = i;
++a;
}
printf("%d\n", a);
}
}
return 0;
}
C. Double-ended Strings
풀이 보기
풀이
이 문제의 총평은 한줄로 요약할 수 있을 것 같다. “개같은 C”..
우선 주어진 문장은 앞뒤에서만 지워나갈 수 있기 때문에, 문장이 끊어졌다가 이어지는 경우는 없다. 결국 search에 사용할 문장들은 모두 original의 substring들이다.
가장 긴 substring부터 하나하나 순차적으로 찾는 방법을 사용했다. python이나 java 썼으면 substring[a:b]랑 search 등으로 시간을 많이 줄일 수 있었을 것 같다..
코드
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
#include <stdio.h>
#define MAX_LEN 20
#define True 1
#define False 0
typedef char boolean;
char str[2][MAX_LEN + 1];
int strlen(char* st) {
int i;
for (i = 0; st[i]; ++i);
return i;
}
#define min(a, b) (((a) > (b)) ? (b) : (a))
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%s %s", str[0], str[1]);
int len[2] = { strlen(str[0]), strlen(str[1]) };
int k = len[0] + len[1];
int l;
for (int i = len[1]; i > 0; --i) {
for (int j = 0; j + i <= len[1]; ++j) {
l = 0;
while (l + i <= len[0]) {
if (str[0][l] == str[1][j]) {
boolean isSame = True;
for (int a = 0; a < i; ++a) {
isSame &= (str[0][l + a] == str[1][j + a]);
}
if (isSame) {
l = 9999;
k -= (i * 2);
}
else {
++l;
}
}
else {
++l;
}
}
if (l == 9999) {
break;
}
}
if (l == 9999) {
break;
}
}
printf("%d\n", k);
}
return 0;
}
D. Epic Transformation
풀이 보기
풀이
똑같은 숫자는 지울 수 없고, 다른 숫자는 1:1로 서로 제거할 수 있다. 그래서, 우선 똑같은 숫자가 몇개씩 있는지 미리 계산해놓아야한다.
그리고 제거할 수 있는 숫자를 하나씩 제거해나가는 방법을 택했다. 가장 많이 있는 숫자 2개를 골라서 하나씩 제거하는 방법을 택했다. 가장 많이 존재하는 수를 빠르게 찾기 위해서 stl의 우선순위 큐를 사용했다.
확실하게 계산하기 위해서 1개씩 지우는 방법을 택했는데, 시간 안에 작동한다는 것이 조금 애매하다. 아마 Div.2에서는 tle가 날 것이다.
더 좋은 방법은 가장 많이 있는 숫자를 m이라고 정의하였다면, max(n % 2, 2 * m - 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
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
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX_LEN 200000
struct cmp {
bool operator()(int a, int b) {
return a < b;
}
};
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
int arr[MAX_LEN];
for (int i = 0; i < n; ++i) {
scanf("%d", arr + i);
}
priority_queue<int, vector<int>, cmp> pq;
sort(arr, arr + n);
int temp = 1;
for (int i = 1; i < n; ++i) {
if (arr[i] != arr[i - 1]) {
pq.push(temp);
temp = 1;
}
else {
++temp;
}
}
pq.push(temp);
int result = 0;
while (!pq.empty()) {
int a = pq.top();
pq.pop();
if (pq.empty()) {
result = a;
break;
}
else {
int b = pq.top();
pq.pop();
if (a > 1) {
pq.push(a - 1);
}
if (b > 1) {
pq.push(b - 1);
}
}
}
printf("%d\n", result);
}
return 0;
}
E. Restoring the Permutation
풀이 보기
풀이
간단하다. 직관적인 문제이다. 배열의 값 $q_{i}$는 이전에 나온 수들 중에서 최댓값을 의미한다. 따라서 이 값이 바뀌는 지점은 그 값을 사용하여야한다는 의미이다. 예를 들어 $q_{i}$값이 3으로 바뀌는 순간이 있다면, 원래 배열에서도 그 위치의 값은 3이고, 이후에는 1과 2를 사용하여 자리를 채울 수 있다는 의미이다.
따라서 값이 바뀌는 지점에서의 배열값 $a_{i}$는 $q_{i}$를 사용하고, 변경되지 않는다면 사용 가능한 수들로 최대 / 최소의 순열을 만들어나가면 된다.
구현에는 우선순위 큐를 사용했다. 최소 힙과 최대 힙 2개를 사용하여 각 힙에 따라 최대 순열 / 최소 순열을 뽑아낼 수 있도록 하였다.
코드
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
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct gcmp {
bool operator()(int a, int b) {
return a < b;
}
};
struct lcmp {
bool operator()(int a, int b) {
return a > b;
}
};
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
int x = 0;
int used = 1;
vector<int> minV, maxV;
priority_queue<int, vector<int>, gcmp> pq1;
priority_queue<int, vector<int>, lcmp> pq2;
for (int i = 0; i < n; ++i) {
int a;
scanf("%d", &a);
if (x != a) {
x = a;
minV.push_back(x);
maxV.push_back(x);
for (; used < x; ++used) {
pq1.push(used);
pq2.push(used);
}
used = x + 1;
}
else {
minV.push_back(pq2.top());
maxV.push_back(pq1.top());
pq1.pop();
pq2.pop();
}
}
for (int i : minV) {
printf("%d ", i);
}
printf("\n");
for (int i : maxV) {
printf("%d ", i);
}
printf("\n");
}
return 0;
}
결과
| Contest | Start time | Rank | Solved | Rating change | New rating |
|---|---|---|---|---|---|
| #710 (Div. 3) | 2021/3/25 23:35 | 829 | 5 | +39 | 1540 |
7문제 중 무려 5문제나 풀어냈다!
문제가 쉬운 감도 있었다. E까지 풀고 G번 문제를 보았는데, 직관적으로 방법은 떠오를 정도였다. 다만 E를 푼 이후 시간이 11분이었어서 시도는 제대로 하지 못했다. 에디토리얼을 보았는데 방법도 약간 다르다. 아마 1시간 정도의 시간이 있었으면 어느 정도까지는 풀 수 있지 않았을까 아쉬움도 남는다.
꾸준히 해서 contest의 모든 문제를 풀어보는 날을 만들어야겠다고 생각한다. 시간이 안따라주는 것은 많이 아쉽다. 성공하려면 내 시간을 더 쪼개야겠지.. 이번 학기에는 이전과는 차원이 다른 바쁜 삶을 살게 될 것 같다..