두번째 SCPC 도전이다. 작년에도 시도했던 대회이니만큼 작년보다는 더 좋은 성적을 내겠다는 다짐으로 도전하였다.
이번 1라운드에서는 맞은 문제 자체는 크게 바뀌지 않았지만 전체적인 시도횟수가 많이 줄었다. 코드를 한번 짤때 정확도가 늘었다고 생각할 수 있을까?
체감 난이도도 작년에 비해서 높아진 것 같았다. 작년에는 3번까지 dp만 하면 됐었는데..
Q1. 친구들
풀이 보기
시도 횟수 : 1 / 10
점수 : Pass ( 80 / 80, 0.18134 )
풀이
문제를 처음 보자마자 유니온파인드 문제임을 직감했다. 한 사람이 “이 사람과 나는 친구관계다” 라는 정보를 담은 배열이 주어지고, 그것은 단방향이어도 상관없으므로, 정보가 주어질 때마다 두개의 집합을 합쳐 친구관계를 모아버리면 된다. 끝까지 수행한 이후 남는 집합의 개수가 정답이 된다.
다른 풀이로는 dfs를 이용한 visit를 이용하는 방법이 있다고 한다. 내 방식보다 훨씬 빠른 수행시간을 보일 수 있을 것 같은데, 이후에 재시도할 때 시도해봐야겠다.
소스코드
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
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
#define MAX (int)(1e5 + 1)
int parent[MAX];
int input[MAX];
int result;
int find(int x) {
if (parent[x] == x) {
return x;
} else {
return parent[x] = find(parent[x]);
}
}
bool merge(int a, int b) {
int x = find(a), y = find(b);
if (x == y) {
return false;
} else {
if (x > y) {
parent[a] = parent[x] = y;
} else {
parent[b] = parent[y] = x;
}
return true;
}
}
int main() {
int testcase;
scanf("%d", &testcase);
for (int T = 1; T <= testcase; ++T) {
int n;
scanf("%d", &n);
result = n;
for (int i = 1; i <= n; ++i) {
parent[i] = i;
scanf("%d", input + i);
}
for (int i = 1; i <= n; ++i) {
if (i + input[i] <= n) {
result -= merge(i, i + input[i]);
}
}
printf("Case #%d\n%d\n", T, result);
}
return 0;
}
Q2. 이진수
풀이 보기
시도 횟수 : 3 / 10
점수 : Pass ( 150 / 150, 0.03875 )
풀이
정확한 풀이방식이 떠오르지 않는다. 수많은 if문에서 볼 수 있듯이, case work로 풀어낸 문제이다.
우선 문제 조건에 따라 정답을 도출하는 경우를 2가지로 나눌 수 있다.
- $t$가 $n$의 절반보다 작거나 같은 경우
- $t$가 $n$의 절반보다 큰 경우
우선 1번 상황에서의 풀이 방식은 아래와 같다.
- B의 배열의 값에 따라 A의 배열 값이 정해지는 구간이 존재한다. 그 부분은 값을 미리 지정한다. ( 첫 2개의 for문 )
- 다음으로는 배열을 모두 순회하며 값을 지정한다.
- 만약 B의 배열 값이 $0$이라면 A에서 그 부분을 지정하는 모든 부분의 값은 $0$이어야한다. ( 다만 범위를 벗어나는 경우 런타임 에러 방지를 위해 미리 범위를 판단한 후 접근하자 )
- 만약 B의 배열 값이 $1$이라면 그곳을 지정하는 A의 배열 2개의 부분은 아래와 같은 절차를 따른다.
- 만약 어느 한쪽이 사용 불가능한 위치라면, 다른 부분의 배열 값은 $1$이어야 한다.
- 만약 어느 한쪽의 배열 값이 $0$으로 지정되었다면, 다른 부분의 배열 값은 $1$이어야 한다.
- 만약 어느 한쪽의 배열 값이 $1$로 지정되었다면, 다른 부분의 배열 값은 우선 Unknown으로 지정되있는 채로 넘긴다.
- 만약 두 부분 모두 Unknown이라면 뒷부분의 가능성을 염두에 두고 아래 절차를 따른다.
- 뒷부분을 이용하여 B의 값을 만드는 부분의 배열 값이 $1$인 경우 뒷부분에 $1$을 제공함으로써 문제의 조건인 정답 문자열은 항상 최소여야한다를 유지한다.
- 만약 뒷부분에서 $0$이 나와 뒤에 $1$을 추가할 수 없는 경우 앞부분에 $1$을 지정한다.
다음으로 2번 상황에서의 풀이 방식은 아래와 같다.
- B의 배열의 값에 따라 A의 배열 값이 정해지는 구간이 존재한다. 그 부분은 값을 미리 지정한다. ( 첫 2개의 for문 )
- 그 이외의 부분은 모두 $0$이어야한다. ( 지정할 수 있는 부분이 없음 )
시도횟수가 3번인데, 처음 2번 경우에서 초반에 모든 정답을 Unknown으로 지정해주는데, 이후 단계에서 이것을 Zero로 바꾸지 않아 222222와 같은 답이 출력되어 생긴 문제였다.
소스코드
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
#define MAX (int)(5e4 + 1)
#define ZERO '0'
#define ONE '1'
#define UNKNOWN '2'
int n;
char A[MAX];
char B[MAX];
bool canPlace(int x) {
return (0 <= x && x < n);
}
int main() {
int testcase;
scanf("%d", &testcase);
for (int T = 1; T <= testcase; ++T) {
int t;
scanf("%d %d", &n, &t);
scanf("%s", B);
A[n] = '\0';
for (int i = 0; i < n; ++i) {
A[i] = UNKNOWN;
}
if (2 * t <= n) {
for (int i = 0; i < t; ++i) {
A[i + t] = B[i];
}
for (int i = n - t; i < n; ++i) {
A[i - t] = B[i];
}
for (int i = t; i < n - t; ++i) {
if (B[i] == ZERO) {
if (canPlace(i + t)) {
A[i + t] = ZERO;
}
if (canPlace(i - t)) {
A[i - t] = ZERO;
}
} else {
if (canPlace(i - t)) {
if (canPlace(i + t)) {
if (A[i + t] == ZERO) {
A[i - t] = ONE;
} else if (A[i + t] == ONE) {
} else {
if (A[i - t] == ZERO) {
A[i + t] = ONE;
} else if (A[i - t] == ONE) {
} else {
int temp = i + 2 * t;
if (!canPlace(temp) || B[temp] == ONE) {
A[i + t] = ONE, A[i - t] = ZERO;
} else {
A[i + t] = ZERO, A[i - t] = ONE;
}
}
}
} else {
A[i - t] = ONE;
}
} else {
A[i + t] = ONE;
}
}
}
//printf("t : %s\n", A);
for (int i = 0; i < n; ++i) {
if (A[i] == UNKNOWN) {
A[i] = ZERO;
}
}
} else {
for (int i = t; i < n; ++i) {
A[i - t] = B[i];
}
for (int i = 0; i < n - t; ++i) {
A[i + t] = B[i];
}
for (int i = 0; i < n; ++i) {
if (A[i] == UNKNOWN) {
A[i] = ZERO;
}
}
}
printf("Case #%d\n%s\n", T, A);
}
return 0;
}
Q3. No Cycle
풀이 보기
시도 횟수 : 2 / 10
점수 : Pass ( 180 / 180, 0.60013 )
풀이
사이클이 생기지 않도록 간선의 방향을 정하는 문제이다.
이 풀이에서 사용하는 기본적인 알고리즘은 ‘플로이드-와샬’ 알고리즘을 개량한 것이다. bool 형식의 matrix는 2차원 배열로 지정하고, 아래와 같은 의미를 가지고 있게 설계했다.
- matrix[i][j]가 $0$이라면, i -> j 로 가는 경로가 존재하지 않는다.
- matrix[i][j]가 $1$이라면, i -> j 로 가는 경로가 존재한다.
풀이법은 아래와 같은 순서를 따랐다.
- 먼저 matrix 배열을 초기화한다. 모든 위치에서 다른 위치로 가는 경우는 존재하지 않고, 자신으로 가는 경로는 존재한다고 지정한다.
- 이미 방향이 지정된 간선들을 입력받는다. 그 간선들에 대해서는 matrix의 값을 업데이트한다.
- 방향이 지정되지 않은 간선들의 입력을 받는다. 그 중에서 이미 간선의 방향이 정해져야하는 간선들의 값은 미리 지정한다. 이 값은 ret 문자열에 지정해둔다.
- matrix의 값을 모두 업데이트한다. i -> j 로 가는 경로가 있다면 모든 부분의 값을 true로 바꿔주어야한다.
- 방향이 지정되지 않은 간선이 존재하는 경우 계속 반복한다.
- 모든 간선에 대해서 방향이 지정 가능한지 판단한다. 판단하는 방법은 반대의 간선을 추가하면 사이클이 발생하는가에 대한 여부이다.
- 만약 한번의 반복에서 방향이 지정되는 간선이 없는 경우, 두 개의 집합이 서로 묶이지 않은 경우이고, 이 경우에는 아무 간선이나 아무 방향으로 설치하더라도 사이클이 발생하지 않는다. 문제에서 주어진 조건에서 정답 문자열은 항상 최소의 값을 가져야하므로, 방향이 지정되지 않은 가장 빠른 간선의 방향을 정방향으로 지정하는 것으로 조건을 유지하자.
- 이 때 지정한 간선에 의해 matrix의 값이 바뀌어야하므로 추가로 업데이트해준다.
- 전체 결과를 출력한다.
시간초가 $O(n^3)$에 돌아가지 않을 것이라는 편견에 사로잡혀 바로 시도하지 않았는데, 이럴줄 알았으면 빠르게 시도하고 4번 문제를 풀었으면 좋은 결과를 가지지 않았을까 후회하고 있다.
소스코드
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <stdio.h>
typedef struct Path {
int s, e;
} PT;
typedef char bool;
const bool true = 1;
const bool false = 0;
#define RIGHT '0'
#define BACK '1'
#define UNKNOWN '2'
#define MAX 500 + 1
bool matrix[MAX][MAX + 1];
PT path[2000];
char ret[2001];
int n, m, k;
int main() {
int testcase;
scanf("%d", &testcase);
for (int T = 1; T <= testcase; ++T) {
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
matrix[i][j] = (i == j);
}
}
for (int i = 0; i < m; ++i) {
int a, b;
scanf("%d %d", &a, &b);
matrix[a][b] = true;
}
ret[k] = '\0';
int unknown = 0;
for (int i = 0; i < k; ++i) {
int a, b;
scanf("%d %d", &a, &b);
path[i] = (PT){a, b};
if (matrix[a][b] == true) {
ret[i] = RIGHT;
} else if (matrix[b][a] == true) {
ret[i] = BACK;
} else {
ret[i] = UNKNOWN;
++unknown;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
matrix[j][k] |= (matrix[j][i] && matrix[i][k]);
}
}
}
while (unknown > 0) {
bool isChanged = false;
for (int i = 0; i < k; ++i) {
if (ret[i] == UNKNOWN) {
if (matrix[path[i].s][path[i].e] == true) {
ret[i] = RIGHT;
isChanged = true;
--unknown;
} else if (matrix[path[i].e][path[i].s] == true) {
ret[i] = BACK;
isChanged = true;
--unknown;
} else {
}
}
}
if (!isChanged) {
for (int i = 0; i < k; ++i) {
if (ret[i] == UNKNOWN) {
--unknown;
ret[i] = RIGHT;
for (int j = 1; j <= n; ++j) {
if (matrix[j][path[i].s] == true) {
matrix[j][path[i].e] = true;
for (int k = 1; k <= n; ++k) {
if (matrix[path[i].e][k] == true) {
matrix[j][k] = true;
}
}
}
}
break;
}
}
}
}
printf("Case #%d\n%s\n", T, ret);
}
return 0;
}
Q4. 예약 시스템
풀이 보기
시도 횟수 : 2 / 10
점수 : Pass ( 88 / 190, 1.23966 )
풀이
전체 테스트케이스는 맞지 못했지만 부분점수를 받은 문제이다. 이 문제의 테스트케이스는 아래와 같았다.
- 모든 손님 집합의 원소 수가 짝수인 경우 ( O )
- 모든 손님 집합의 원소 수가 홀수인 경우 ( O )
- 손님 집합의 원소 수가 섞여있는 경우 ( X )
우선 모든 손님 집합의 정보를 기록한다. 다만 기록하는 과정은 아래와 같다.
- 원소의 개수가 홀수인 경우 / 짝수인 경우를 따로 기록한다.
- 원소의 숫자들을 저장할 때에는 그 중에서 가장 작은 값을 가지는 4개의 수만을 기록한다. 계산에는 이 4개의 숫자만을 사용할 것이다.
이후 먼저 모든 값을 더하여 기록한다. 이 때 짝수는 모든 수를 1번씩, 홀수는 모든 수를 1번씩에 추가로 가장 작은 수를 한번 더 사용해야한다. ( 모양에 따른 추가 간섭 발생 )
이후 모든 홀수원소는 합쳐 짝수 블럭으로 변환하였다. 변환할 때에는 가장 큰 수 2개를 가장자리로 보내고 합쳐서 추가하였다.
이후에는 가장 큰 원소를 가진 2개의 블럭을 가장자리로 보내 결과값을 가장 작게 조절한다. 풀이에는 모든 블럭을 정렬하여 구했다.
홀수 + 짝수의 경우가 제대로 구현되지 않은 것이 만점을 받지 못한 원인인 것 같다. 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
#include <stdio.h>
typedef struct Node {
int minA[4];
} Node;
#define MAX_NUM (int)1e5
#define MAX_GROUP (int)2e4
int input[MAX_NUM];
Node even[MAX_GROUP + 10000];
int even_len;
Node odd[MAX_GROUP];
int odd_len;
int n, m;
long long result;
int cmp1(int* a, int* b) {
return *a > *b;
}
int cmp2(Node* a, Node* b) {
return (a->minA[2] + a->minA[3]) > (b->minA[2] + b->minA[3]);
}
int main() {
int testcase;
scanf("%d", &testcase);
for (int T = 1; T <= testcase; ++T) {
scanf("%d %d", &n, &m);
result = 0, even_len = 0, odd_len = 0;
for (int i = 0; i < n; ++i) {
int a;
scanf("%d", &a);
for (int j = 0; j < a; ++j) {
scanf("%d", input + j);
}
qsort(input, a, sizeof(int), cmp1);
if (a & 1) {
odd[odd_len++] = (Node){ {input[0], input[1], input[2], input[3]} };
result += (input[0] + input[1] + input[2] + input[3]);
result += input[0];
} else {
even[even_len++] = (Node){ {input[0], input[1], input[2], input[3]} };
result += (input[0] + input[1] + input[2] + input[3]);
}
}
qsort(odd, odd_len, sizeof(Node), cmp2);
int temp = odd_len >> 1;
for (int i = 0; i < temp; ++i) {
input[0] = odd[i].minA[2], input[1] = odd[i].minA[3], input[2] = odd[odd_len - i - 1].minA[2], input[3] = odd[odd_len - i - 1].minA[3];
qsort(input, 4, sizeof(int), cmp1);
even[even_len++] = (Node){ {input[0], input[1], input[2], input[3]} };
}
if (even_len == 1) {
result -= (even[0].minA[0] + even[0].minA[1] + even[0].minA[2] + even[0].minA[3]);
} else {
qsort(even, even_len, sizeof(Node), cmp2);
result -= (even[even_len - 1].minA[3] + even[even_len - 1].minA[2] + even[even_len - 2].minA[3] + even[even_len - 2].minA[2]);
}
printf("Case #%d\n%lld\n", T, result);
}
return 0;
}
결과
작년과 같은 수순을 밟아가는 것 같다. 1년동안 달라진 내 실력은 2라운드에서 검증할 수밖에 없다. 이번에는 작년보다 더 좋은 결과를 받을 수 있기를 희망한다.