Codeforces Round #1113 (Div. 2) 후기
- Codeforces Round #1113 (Div. 2) 후기
A. You Delete, I Delete
풀이 보기
풀이
Alice는 문자열에서 0 하나를 지워 최종 문자열을 사전순으로 최대화하고, 그 다음 Bob은 1 하나를 지워 문자열을 사전순으로 최소화한다.
먼저 Alice의 선택을 생각해보자. 문자열에서 앞쪽에 있는 0을 지울수록, 그 위치 뒤에 있던 문자가 앞으로 당겨진다. 두 0의 위치를 $i<j$라고 할 때 각각을 지운 결과를 비교하면, $i$ 이전까지는 두 문자열이 동일하다. 하지만 $i$번째 위치에서는 앞의 0을 지운 문자열이 더 뒤의 문자를 가지게 되고, 다른 선택에서는 아직 0이 남아있다. 따라서 Alice는 가장 앞에 있는 0을 지우는 것이 항상 최선이다.
Bob의 선택도 같은 방식으로 생각할 수 있다. Bob은 결과를 사전순으로 최소화해야 하므로, 앞쪽의 1을 지워 뒤의 문자를 앞으로 당기는 것이 이득이다. Alice가 0을 하나 지웠더라도 1들의 상대적인 순서는 달라지지 않으므로, Bob은 원래 문자열에서 가장 앞에 있는 1을 지우면 된다.
결론적으로 원래 문자열을 왼쪽부터 순회하면서, 처음 만나는 0 하나와 처음 만나는 1 하나를 출력하지 않으면 정답을 얻을 수 있다.
시간복잡도는 문자열의 길이를 $n$이라고 할 때 $O(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
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
#define MAX_IDX 100
char str[MAX_IDX + 1];
int main() {
int tc;
scanf("%d", &tc);
while (tc--) {
scanf("%s", str);
bool zero_removed = false, one_removed = false;
for (int i = 0; str[i] != '\0'; ++i) {
if (zero_removed == false && str[i] == '0') {
zero_removed = true;
continue;
} else if (one_removed == false && str[i] == '1') {
one_removed = true;
continue;
} else {
printf("%c", str[i]);
}
}
printf("\n");
}
return 0;
}
B. Merge to Match
풀이 보기
풀이
배열 $a$에서 두 수 $x\le y$를 골라 제거하고, $x\le z\le y$인 수 $z$ 하나를 새로 넣을 수 있다. 여러 번의 연산 뒤에 배열의 순서를 자유롭게 바꿀 수 있으므로, 두 배열을 먼저 오름차순 정렬해서 생각하자.
한 번의 연산은 원소 두 개를 하나로 합치므로 배열의 길이를 정확히 $1$ 줄인다. 또한 문제에서 $a$와 $b$에 등장하는 모든 수가 서로 다르다고 했다. 따라서 최종 배열의 원소 $b_i$가 기존 원소 하나를 그대로 사용해서 만들어지는 경우는 없다. 각 $b_i$를 만들기 위해서는 최소 두 개의 원소가 필요하므로 반드시 다음 조건을 만족해야 한다.
\[n \ge 2m\]이제 정렬된 배열에서 $i$번째로 작은 목표값 $b_i$를 생각해보자. $b_i$보다 작거나 같은 결과를 $i$개 만들기 위해서는 적어도 $i$개의 원래 원소가 필요하므로, $b_i$는 $a_i$보다 커야 한다. 반대쪽에서도 같은 논리를 적용하면 $b_i$는 뒤에서 $m-i$개를 제외한 원소보다 작아야 한다.
0-indexed 배열을 기준으로 조건을 쓰면 다음과 같다.
\[a_i < b_i < a_{n-m+i}\]부등호가 엄격한 이유는 모든 입력 원소가 서로 다르기 때문이다.
이 조건은 필요할 뿐만 아니라 충분하기도 하다. 각 $i$에 대해 $a_i$와 $a_{n-m+i}$를 하나의 쌍으로 잡으면, 두 수 사이에 $b_i$가 존재하므로 그 쌍을 합쳐 $b_i$를 만들 수 있다. $n\ge 2m$이므로 이 쌍들은 서로 겹치지 않는다. 쌍을 만들고 남는 가운데 원소들은 이미 만든 결과 중 하나와 추가로 합쳐도 그 결과를 그대로 유지하도록 처리할 수 있다.
따라서 정렬 후 모든 $i$에 대해 위 구간 조건을 검사하면 된다. 시간복잡도는 정렬이 지배하므로 $O(n\log n+m\log m)$이다.
코드
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>
#include <stdlib.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
#define MAX_IDX (int)(2e5)
int a[MAX_IDX], b[MAX_IDX];
int asc(const void* a, const void* b) {
if (*(int*)a > *(int*)b) {
return 1;
} else if (*(int*)a < *(int*)b) {
return -1;
} else {
return 0;
}
}
int main() {
int tc;
scanf("%d", &tc);
while (tc--) {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
for (int i = 0; i < m; ++i) {
scanf("%d", &b[i]);
}
qsort(a, n, sizeof(int), asc), qsort(b, m, sizeof(int), asc);
if (a[0] > b[0] || a[n - 1] < b[m - 1]) { // error case 1
printf("NO\n");
continue;
} else if (n < 2 * m) { // error case 2 :: all elements are different
printf("NO\n");
continue;
}
bool is_possible = true;
for (int i = 0; i < m; ++i) {
int lower = a[i];
int upper = a[n - m + i];
if ((lower < b[i] && b[i] < upper) == false) {
is_possible = false;
break;
}
}
printf(is_possible ? "YES\n" : "NO\n");
}
return 0;
}
C. Maximize the Score
풀이 보기
풀이
배열에는 $1$부터 $n$까지의 수가 정확히 두 번씩 등장한다. 어떤 수 $x$를 선택하면 현재 배열에서 $x$의 두 위치 사이를 전부 지우고, 지운 구간 길이의 제곱을 점수에 더한다.
처음에는 앞선 연산으로 내부 원소가 사라진 뒤 더 짧아진 구간을 지우는 경우도 고려해야 할 것처럼 보인다. 하지만 제곱 함수의 성질을 이용하면, 어떤 수의 두 등장 위치 사이를 지울 것이라면 원래 구간 전체가 남아있을 때 먼저 지워도 손해가 없다는 것을 알 수 있다.
길이가 $A$인 바깥 구간 안에서 길이가 $B$인 구간을 먼저 지웠다고 하자. 그 뒤 바깥 구간을 지우면 얻는 점수는 최대
\[(A-B)^2+B^2\]이다. 반대로 바깥 구간을 먼저 지우면 $A^2$을 얻으며,
\[(A-B)^2+B^2 \le A^2\]가 성립한다. 따라서 내부 삭제를 뒤로 미루고 바깥 구간을 먼저 삭제해도 점수가 감소하지 않는다.
결국 문제는 원래 배열을 서로 겹치지 않는 블록들로 나누는 문제로 바뀐다. 각 블록은 다음 둘 중 하나다.
- 원소 하나만 포함하는 길이 $1$의 블록
- 양 끝의 값이 같은 하나의 완전한 구간
각 블록은 길이의 제곱만큼 점수를 준다. 이제 prefix DP를 적용할 수 있다.
dp[i]를 배열의 앞 $i$개 원소를 모두 처리했을 때 얻을 수 있는 최대 점수라고 정의하자. 다음 원소 하나만 따로 지우는 경우에는 점수가 $1$ 증가한다.
현재 위치 $i$가 어떤 값의 두 번째 등장이고, 첫 등장 위치가 first라면 구간 $[first,i]$ 전체를 하나의 블록으로 선택할 수 있다. 그 경우에는 그 구간 앞까지의 최적값에 구간 길이의 제곱을 더한다.
각 수의 첫 등장 위치를 배열에 기록해두면 모든 상태를 한 번씩만 계산할 수 있다. 시간복잡도는 $O(n)$이며, 실제 배열 길이가 $2n$이므로 정확히는 $O(2n)$이다.
코드
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
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
typedef long long ll;
#define MAX_IDX (int)(2e5)
const int NONE = -1;
int arr[MAX_IDX * 2 + 1];
int number_first_apperance[MAX_IDX + 1];
ll dp[MAX_IDX * 2 + 1];
#define max(a, b) (((a) > (b)) ? (a) : (b))
int main() {
int tc;
scanf("%d", &tc);
while (tc--) {
int n;
scanf("%d", &n);
for (int i = 0; i < 2 * n; ++i) {
scanf("%d", arr + i);
}
for (int i = 1; i <= n; ++i) {
number_first_apperance[i] = NONE;
}
for (int i = 0; i < 2 * n; ++i) {
int cur = arr[i];
dp[i + 1] = dp[i] + 1;
if (number_first_apperance[cur] == NONE) {
number_first_apperance[cur] = i;
} else {
int first = number_first_apperance[cur];
dp[i + 1] = max(dp[i + 1], dp[first] + (i - first + 1LL) * (i - first + 1LL));
}
}
printf("%lld\n", dp[2 * n]);
}
return 0;
}
D. Good Pair Queries
풀이 보기
풀이
같은 위치에 있는 두 문자열의 문자를 하나의 쌍으로 보면, 각 위치는 다음 네 종류 중 하나가 된다.
- $(0,0)$
- $(0,1)$
- $(1,0)$
- $(1,1)$
어떤 구간에서 각 종류의 개수를 각각 $u,x,y,v$라고 하자. 여기서 $u$는 $(0,0)$, $x$는 $(0,1)$, $y$는 $(1,0)$, $v$는 $(1,1)$의 개수이다.
문자열 쌍이 good하기 위한 필요충분조건은 다음과 같다.
직관적으로 $(0,1)$과 $(1,0)$은 서로 한 개씩 짝지어 함께 제거할 수 있다. 두 종류의 개수가 다르면 더 많이 남은 혼합 쌍을 처리해야 하는데, $(0,0)$ 또는 $(1,1)$처럼 두 문자열의 문자가 같은 위치가 그 차이를 하나씩 흡수해줄 수 있다. 따라서 혼합 쌍 개수의 차이가 같은 문자 쌍의 전체 개수보다 크면 절대로 모두 제거할 수 없다.
반대로 위 조건을 만족한다면, $(0,1)$과 $(1,0)$을 가능한 만큼 서로 짝지은 다음 남는 혼합 쌍들을 $(0,0)$ 또는 $(1,1)$과 짝지을 수 있다. 같은 문자 쌍은 어떤 종류와도 적절한 mode를 선택하여 함께 제거할 수 있으므로 전체를 비울 수 있다.
코드에서는 네 종류를 모두 따로 세지 않고 조건에 필요한 값만 압축해서 저장했다.
prefix_same: $(0,0)$과 $(1,1)$의 개수, 즉 $u+v$prefix_rightBig: $(0,1)$이면 $+1$, $(1,0)$이면 $-1$을 더한 값, 즉 $x-y$
그러면 각 쿼리 $[l,r]$에 대해 누적합으로 same과 balance를 $O(1)$에 구할 수 있고, 다음 조건만 검사하면 된다.
전처리는 $O(n)$, 각 쿼리는 $O(1)$이므로 전체 시간복잡도는 $O(n+q)$이다.
코드
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
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
#define MAX_IDX (int)(2e5)
char a[MAX_IDX + 1], b[MAX_IDX + 1];
int prefix_same[MAX_IDX + 1], prefix_rightBig[MAX_IDX + 1];
int main() {
int tc;
scanf("%d", &tc);
while (tc--) {
int n, q;
scanf("%d %d", &n, &q);
scanf("%s %s", a, b);
// preprocessing :: count 0, 1 from string [prefix sum!]
prefix_same[0] = 0, prefix_rightBig[0] = 0;
for (int i = 0; i < n; ++i) {
prefix_same[i + 1] = prefix_same[i], prefix_rightBig[i + 1] = prefix_rightBig[i];
if (a[i] == b[i]) {
prefix_same[i + 1] += 1;
} else if (a[i] == '0' && b[i] == '1') {
prefix_rightBig[i + 1] += 1;
} else { /* a[i] == '1' && b[i] == '0' */
prefix_rightBig[i + 1] -= 1;
}
}
while (q--) {
int l, r;
scanf("%d %d", &l, &r);
// processing :: compare counting in certain range
int same = prefix_same[r] - prefix_same[l - 1];
int balance = prefix_rightBig[r] - prefix_rightBig[l - 1];
if (same >= abs(balance)) {
printf("YES\n");
} else {
printf("NO\n");
}
}
}
return 0;
}
여담
생각해보니, 구현할 때 abs() 함수를 정의하지 않았는데 통과되었다. 아마 컴파일러 단계에서 자동으로 추가된 것 같은데, 의도치 않은 감점을 당할 뻔했다.
결과
| Contest | Start time | Rank | Solved | Rating change | New rating |
|---|---|---|---|---|---|
| #1113 (Div. 2) | 2026/08/01 23:35 | 1922 | 4 | +7 | 1577 |