contest 뒤에 바로 contest, 사실 학기 중에 하고 싶었으나 하지 못했던 것을 몰아서 하고 싶어서 바로 신청했다. 이전 contest에서 결과가 좋지 않아서 이번에는 얼마나 rate가 떨어질까 걱정된다.
A. Contest Start
풀이 보기
풀이
A 문제 치고 엄청 까다로운 문제였다. 실제로 통계로도 A 문제를 푼 사람보다 B문제를 푼 사람이 더 많다. 수학 문제치고 고려할 부분이 많은 문제이다.
기본적인 사항을 정리해보자.
우선 가장 뒤에 contest를 끝내는 사람의 dissatisfaction은 $0$이다. 그 이전에 contest를 끝낸 사람의 dissatisfaction은 $1$이다. 이런 식으로 계속 1씩 증가하다가 증가가 끝나는 지점은 특정 사람의 dissatisfaction이 $t / x$가 되는 시점이 될 것이다.
문제는 contest에 참여한 사람들의 수로 수열을 만들 때 최대로 증가할 수 있는 수가 정해져 있다는 것이다. 사람의 수 $n$이 충분히 크다면 $0$부터 시작해서 $t / x$까지 증가하는 dissatisfaction을 만들고 나머지 사람들의 dissatisfaction을 $t / x$로 계산해서 더할 수 있지만, $n$이 작다면 첫 번째 사람이 contest를 끝내기 전에 사람이 부족해져 dissatisfaction이 $t / x$에 미치지 못하는 경우가 발생한다.
위 사항을 생각하여 고려 사항을 간단히 정리하면 아래와 같다.
- $n$이 충분히 크다면 $0$부터 시작하여 $t / x$로 끝나는 공차가 1인 등차수열을 만들고 나머지 사람들의 dissatisfaction을 $t / x$로 계산 가능하다.
- $n$이 작다면 $0$부터 시작하여 $n - 1$로 끝나는 공차가 1인 등차수열까지만 만들 수 있다.
위 사항을 생각하며 경우에 따른 값만 정리하면 답을 얻을 수 있다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
int main() {
int k;
scanf("%d", &k);
while (k--) {
long long n, x, t;
scanf("%lld %lld %lld", &n, &x, &t);
long long d = t / x;
if (n >= d + 1) {
printf("%lld\n", ((d) * (d + 1) / 2) + (d * (n - d - 1)));
}
else {
printf("%lld\n", (n - 1) * (n) / 2);
}
}
return 0;
}
B. Love Song
풀이 보기
풀이
문자열에서 알파벳 순서에 따라 몇번 적을지 정해진다고 되있다. ‘a’라면 1번, ‘b’라면 2번 적힌 새로운 문자열을 만들어야하는데, 출력은 숫자만 하면 되므로 글자 수만 세서 저장해두자.
문제에서는 문자열 간격에 대한 쿼리가 여러번 주어지는데, 경험상 처음 주어진 조건에서 바뀌지 않고 여러 쿼리를 수행하는 문제는 dp 등을 이용하여 답을 모두 구한 후 출력하는 방법이 정해라고 생각한다. 그래서 dp 누적합 방법을 이용하여 0부터 k까지의 생성될 글자 수를 저장해두는 방법으로 문제를 풀었다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#define MAX_IDX (int)(1e5 + 1)
int dp[MAX_IDX];
int main() {
int n, q;
scanf("%d %d", &n, &q);
char str[MAX_IDX];
scanf("%s", str);
for (int i = 1; i <= n; ++i) {
dp[i] = dp[i - 1] + str[i - 1] - 'a' + 1;
}
while (q--) {
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n", dp[b] - dp[a - 1]);
}
return 0;
}
여담
1
long long dp[MAX_IDX] = {0};
위의 코드를 main 함수에 넣는 것이 compilation error 결과를 리턴했다. 배열은 전역으로 만들어야할 것 같다.
C. Stable Groups
풀이 보기
풀이
원리는 생각보다 간단한데, 여러모로 애먹은 문제이다.
결론부터 말하자면 그리디 문제이다. 우선 모든 사람들을 오름차순으로 정렬한다. 그리고 사람을 추가하지 않고 서로 묶을 수 있는 그룹인지 검사한다. 만약 사람이 추가로 필요하다면 새로 그룹을 만들고 “필요한 사람 수를 따로 다른 배열에 추가로 저장”한다. 이렇게 하면 사람을 추가하지 않고 만들 수 있는 최소의 그룹의 개수를 구할 수 있다.
이제 사람을 추가하여 그룹을 합치는 작업을 한다. 위에서 저장한 배열을 재정렬하여 작은 순으로 나열하고, 그 순서에 맞춰 $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
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
#include <stdio.h>
typedef unsigned long long ll;
#define MAX_IDX (int)2e5
ll arr[MAX_IDX];
ll result;
ll A[MAX_IDX];
int len;
int n;
ll k, x;
int cmp(ll* a, ll *b) {
if (*a > *b) {
return 1;
}
else if (*a == *b) {
return 0;
}
else {
return -1;
}
}
int main() {
scanf("%d %llu %llu", &n, &k, &x);
for (int i = 0; i < n; ++i) {
scanf("%llu", arr + i);
}
qsort(arr, n, sizeof(ll), cmp);
result = 1;
for (int i = 1; i < n; ++i) {
if (arr[i - 1] + x < arr[i]) {
ll a = (arr[i] - arr[i - 1] - 1) / x;
A[len++] = a;
++result;
}
}
if (len > 0) {
qsort(A, len, sizeof(ll), cmp);
}
for (int i = 0; i < len; ++i) {
if (k >= A[i]) {
--result;
k -= A[i];
}
else {
break;
}
}
printf("%llu", result);
return 0;
}
여담
저번 contest에서도 그랬지만, long long 타입의 qsort 정렬이 이상하다.
1
2
3
int cmp(long long* a, long long* b) {
return *a > *b
}
위의 cmp 함수가 작동하지 않는 것 같다. 심지어 값의 범위가 문제인지 long long도 부족해서 unsigned long long을 대신 사용했다. int에서의 정렬은 제대로 되어서 사용하는 정렬 방법인데, long long에서는 먹히지 않아 시간을 많이 잡아먹는다. cmp 함수를 더 정교하게 만드는 식으로 방향을 잡아야겠다.
D. PriceFixed
풀이 보기
풀이
D번 문제치고는 원리가 간단해서 이해하기가 쉬운 문제였다. 아니 그냥 내가 그리디에 강한건가?
모든 물건의 가격은 기본 $2$원이고 이미 $b_i$개의 물건을 샀다면 $1$원으로 물건을 살 수 있다. 이 때 할인된 가격으로 물건을 사는 것도 $b_i$에 영향을 줄 수 있다.
결국 할인을 최대한 이용하기 위해서는 $b_i$가 가장 큰 물건부터 정가로 사는 방법을 이용하면 된다. 이후 할인을 받을 수 있는 물건들을 $1$원을 주고 사서 물건을 계속해서 구입하고, 그것을 이용하여 다른 물건을 할인받는 연쇄적인 방법을 통하면 최대한 싸게 모든 물건을 구입할 수 있다.
위의 이론을 알고리즘화하여 풀어쓰면 아래 절차와 같다.
- 먼저 모든 물건을 $b_i$의 오름차순으로 정렬한다. 정렬하였다면 가장 앞의 물건을 할인받아 살 물건 순, 뒤의 물건들은 정가로 구매할 물건으로 생각하자.
- 현재 가장 앞의 물건을 할인받아 살 수 있다면 할인받아 사고 다음 물건을 보자.
- 만약 할인받을 수 없다면 뒤의 물건을 사며 앞의 물건을 할인받을 수 있는 상태를 만들자.
- 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <stdio.h>
typedef long long ll;
typedef struct Node {
ll a, b;
} ND;
#define MAX_IDX (int)1e5
ND arr[MAX_IDX];
int n;
ll p;
ll result;
int cmp(ND* a, ND* b) {
if (a->b > b->b) {
return 1;
}
else if (a->b == b->b) {
if (a->a > b->a) {
return 1;
}
else {
return -1;
}
}
else {
return -1;
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
ll a, b;
scanf("%lld %lld", &a, &b);
arr[i] = (ND) { a, b };
}
qsort(arr, n, sizeof(ND), cmp);
int start = 0, end = n - 1;
while (start <= end) {
if (p >= arr[start].b) {
result += arr[start].a;
p += arr[start].a;
++start;
}
else if (start == end) {
ll T = arr[start].b - p;
if (T <= arr[start].a) {
result += (2 * T);
arr[start].a -= T;
p += T;
}
else {
result += (arr[start].a * 2);
p += arr[start].a;
++start;
}
}
else {
if (arr[start].b - p >= arr[end].a) {
result += (2 * arr[end].a);
p += arr[end].a;
--end;
}
else {
ll T = arr[start].b - p;
arr[end].a -= T;
result += (2 * T);
p = arr[start].b;
}
}
}
printf("%lld", result);
return 0;
}
결과
| Contest | Start time | Rank | Solved | Rating change | New rating |
|---|---|---|---|---|---|
| #727 (Div. 2) | 2021/6/20 19:05 | 852 | 4 | +90 | 1582 |
저번 contest와는 매우 상반된 결과다! 개인적으로도 매우 만족스러운 결과이다. C번 문제에서 정렬때문에 시간을 잡아먹은 문제만 아니었다면 4문제 모두 합쳐 1시간 이내로 풀었다. Div.2에서는 최고기록을 달성했다. ( 4 / 6 )
개인적으로 D번 문제까지 난이도가 매우 쉬웠는데 등수가 생각보다 높다. 점수 폭도 크게 상승했다.
1600점까지 18점밖에 남지 않았다! 파란색 닉네임을 얻을 수 있는 가능성이 높아졌다. 더 높은 위치까지 계속해서 올라갈 것이다.