Codeforces라는 문제풀이 페이지를 처음으로 알게 되었고, 그 때에 진행 중이던 이 contest를 참여하였다.
참여할 때에는 몰랐는데, contest는 2시간동안 참여하여 문제를 푸는 형식이었고, 내가 참여하였을 때에는 30분도 남지 않았다. 이미 참가신청은 했기에 최대한 문제를 풀어보자고 생각하고 문제들을 살펴보았다.
contest 기간 중에는 5문제 중 1문제밖에 성공하지 못하였다. 꽤 쉬운 난이도라고는 생각했지만 시간 내에 더 풀어볼 수 없었고, 다음 practice 기간에 시도하여 총 4문제 ( A, B, C, D ) 를 풀어냈다.
A. Candies and Two Sisters
풀이 보기
풀이
$n$개의 캔디가 주어지고 그것을 2명이 나누어 가질 때, $a$가 $b$보다 큰 경우의 수를 구하는 문제이다. 기본적으로 $\frac{1}{2}\times n$가지의 경우의 수가 있다.
$0$개를 주는 경우의 수는 없어야하므로, $n$이 홀수인 경우에는 추가로 1가지의 경우를 더 빼주어야 한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
int main(t) {
for (scanf("%d", &t); t; t--) {
long long n;
scanf("%lld", &n);
if (n < 3) {
printf("0\n");
}
else {
int temp = (n % 2);
n /= 2;
n -= (!temp);
printf("%lld\n", n);
}
}
return 0;
}
B. Construct the String
풀이 보기
풀이
정답 문자열의 모든 $a$ 길이의 substring들은 모두 정확히 $b$개의 문자만으로 이루어지도록 구현하는 문제이다. 규칙이 어렵다고 느낄 수 있지만, 그저 “abcabcabc”와 같이 $b$개의 문자가 반복되도록 문자열을 정하면 모든 경우에서 정답을 출력할 수 있는 간단한 문제이다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int main(t) {
for (scanf("%d", &t); t; t--) {
int n, a, b;
scanf("%d %d %d", &n, &a, &b);
for (int i = 0; i < n; i++)
printf("%c", i % b + 'a');
printf("\n");
}
return 0;
}
C. Two Teams Composing
풀이 보기
풀이
주어진 학생들의 skill level에 대하여 2개의 팀으로 나누는 작업에서, 아래의 조건을 만족하면서 가장 많은 학생을 팀으로 만들 수 있는 경우를 찾는 문제이다.
- 1팀에 속한 모든 학생의 skill level은 달라야 한다.
- 2팀에 속한 모든 학생의 skill level은 같아야 한다.
먼저 1번 팀을 만들 때 가장 많은 학생 수를 $a$로 기록한다. 그리고 2번 팀을 만들 때 가장 많은 학생 수를 $b$로 기록한다. 이 2개의 숫자를 이용하여 최적으로 2개의 팀을 만드는 경우를 탐색한다.
기준은 b의 값을 이용하여 최대를 판별한다. 풀이에서는 총 3가지의 경우를 고려하였다.
- $a≥b+1$인 경우
- 2팀을 $b$명의 학생으로 모두 묶더라도 1팀의 인원을 충족시킬 인원이 있다. 따라서 팀을 꾸릴 수 있는 최대 인원은 $b$명이다.
- $a=b$인 경우
- 2팀을 $b$명의 학생으로 묶는다면 1팀의 인원이 1명 부족하다. 따라서 팀을 꾸릴 수 있는 최대 인원은 $b-1$명이다.
- 그 이외의 경우
- 1팀의 인원을 최대로 하더라도 2팀의 인원을 충족시킬 인원이 있다. 따라서 팀을 꾸릴 수 있는 최대 인원은 $a$명이다.
코드
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
#define max(a, b) (a > b) ? a : b
cmp(int *a, int* b) {
return *a - *b;
}
main(t) {
for (scanf("%d", &t); t; t--) {
int arr[200000];
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", arr + i);
qsort(arr, n, sizeof(int), cmp);
if (n == 1) {
printf("0\n");
continue;
}
int m = 0, temp = 1, count = 1;
for (int i = 1; i < n; i++)
if (arr[i] != arr[i - 1])
m = max(m, temp), temp = 1, count++;
else
temp++;
m = max(m, temp);
int a = m, b = count;
if (a >= b + 1)
printf("%d\n", b);
else if (a == b)
printf("%d\n", b - 1);
else
printf("%d\n", a);
}
return 0;
}
D. Anti-Sudoku
풀이 보기
풀이
최대 9칸을 변경할 수 있다는 조건이 있고, 각 가로줄 또는 세로줄에 공통된 값이 존재해야한다는 조건이 있다. 이를 통해 각각의 줄에서 값을 하나씩만 바꾸는 것으로 anti-sudoku를 만들 수 있다. 그리고 값이 변경되는 위치는 가로 또는 세로에서 각각 겹치지 않아야 한다. 또한 3x3 크기의 정사각형 구역에서도 겹치는 위치가 없어야 한다.
변경되는 값들은 기존 값에서 $1$만큼 증가시켜 이미 있던 수들 중 하나와 같은 값을 가지도록 조절한다. 기본적으로 입력으로 sudoku가 완성되어 주어지므로 가능한 추론이다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
int pos[9] = {
0, 3, 6,
1, 4, 7,
2, 5, 8 };
int main(t) {
for (scanf("%d", &t); t; t--) {
char str[9][10];
for (int i = 0; i < 9; i++) {
scanf("%s", str[i]);
str[i][pos[i]]++;
str[i][pos[i]] -= 9 * (str[i][pos[i]] > '9');
}
for (int i = 0; i < 9; i++)
printf("%s\n", str[i]);
}
return 0;
}
결과
| Contest | Start time | Rank | Solved | Rating change | New rating |
|---|---|---|---|---|---|
| #634 (Div. 3) | 2020/4/13 23:35 | 16046 | 1 | -132 | 1368 |
contest 첫 참여였지만, 시작한 타이밍이 매우 아쉬웠다. practice 기간에 푼 문제들을 contest에서도 풀었다면 꽤 높은 rank까지 올라갔을 것이라 예상한다.
시간이 촉박하다고 작성한 코드를 제대로 확인하지 않고 무작정 제출한 경우가 많았고, 대부분 컴파일 에러를 받았다. contest 중에는 시간에 쫓기지 않고 자신의 페이스를 유지하는 습관을 길러야겠다.