무려 1년이 넘는 시간동안 contest를 하지 않았었다. 애초에 PS 자체를 안하기도 했고, 할 시간도 없었고 해서..
가장 최근에 참여한 contest가 Round 764 (Div. 3) 이다. 무려 작년 1월 개최된 contest다. 현재 rate는 1385, Expert를 찍어봤다고 얘기하기도 무안한 점수다. ( 정리할 필요성도 못 느낄 정도여서, 이 시절의 contest는 따로 정리하지 않을 것 같다 )
최근 어떤 계기로 PS를 다시 깔짝대기 시작했다. 이전과는 다르게 solved.ac 기준 난이도가 높은 문제들을 주로 풀어보았다. 사실 Codeforces contest들의 문제는 수학문제라서 기준이 다르긴 하겠지만, 그래도 이전보다는 낫지 않을까 싶다.
아마 1400점 넘기면 Specialist로 다시 올라가는 것으로 기억한다. 오늘의 목표는 $+15$ 해서 Specialist로 올라갈 것이다.
A. Walking Master
풀이 보기
풀이
문제를 잘 읽어보면, $y$ 좌표는 작아질 수 없다는 사실을 알 수 있다. 다만 $x$좌표는 작아질 수 있다.
$(a, b)$가 $(c, d)$가 되도록 조절을 해야하는데, $b$에서 $d$로 가기 위해서는 1을 계속 더하는 방법밖에 존재하지 않는다. 만약 $b$가 $d$보다 크다면 아예 불가능한 상황.
근데 그것으로 끝나지 않는다. $b$에서 $d$로 가기 위해 $(a, b)$ 좌표를 이동시키면 결과는 $(a + (d - b), d)$일 것이다. 이제 가능한 연산은 $x$좌표를 1 빼내는 연산 뿐. 그러니 $a + (d - b)$가 $c$보다 크거나 같아야한다. 아니라면 그것 또한 불가능한 매칭인 것.
이 2가지 조건만 핸들링하고 아니라면 이동 횟수만 계산하면 끝난다. A번 문제답게 계산 자체는 1줄로 끝나는 문제.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#define abs(x) (((x) < 0) ? (-(x)) : (x))
int main() {
int t;
scanf("%d", &t);
while (t--) {
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
if (b > d || c > a + (d - b)) {
printf("-1\n");
} else {
int e = d - b;
printf("%d\n", e + abs(c - (a + e)));
}
}
return 0;
}
B. Mex Master
풀이 보기
풀이
나름 직관적? 이라고 생각했는데 case를 확인하는데 시간이 너무 쏠린 문제. 실제로 코딩 자체는 얼마 안걸렸는데 이거 증명한다고 쓴 종이만 2장이다. 오히려 MEX가 무엇인지 설명한다고 만들어둔 배열 예시 때문에 더 헷갈린 문제다!
문제에서 얘기하는 MEX는 “배열 안에 없는 음수가 아닌 가장 작은 정수” 라는 의미를 가진다. 물론 $0$ 또한 가능하다. 문제에서는 가능한 가장 작은 MEX를 출력하라고 했으므로, $0$이 가능하다면 가장 이상적인 답일 것이다.
근데 문제에서 배열로 사용하겠다는 것이 입력되는 숫자가 아니라 $a = [a_1+a_2,a_2+a_3,…,a_{n−1}+a_n]$이다. 입력되는 배열 그대로 사용하는 것이 아니라, 인접한 값과 더한 값으로 배열을 사용하겠다는 것. 원소들의 순서는 마음대로 해도 상관 없다고 한다.
풀고나니 문제에서 “Note that you are not required to construct the array $a$ that achieves the minimum score” 라고 말한 이유를 알겠다. 애초에 입력되는 배열을 저장할 이유가 없다는 것. 생각해보니 이 문제를 풀 때 사용한 변수가 단 3개이다..
$0$이 답일 때가 가장 이상적이랬으니, 일단 $0$이 답이도록 상황을 만들어보자. 당연하게도, 배열 안에 0이 없으면 되므로, 모든 원소들을 나열했을 때 $a_k + a_{k+1}$이 0이 되지 않도록 하면 된다. 배열에 있는 원소들 또한 0보다 크거나 같으므로, 2개의 원소의 합이 0이 되는 경우는 둘 다 0인 경우뿐. 문제에서 원소는 어떤 순서로 놓아도 가능하다고 했으므로, 가능하다면 0이 연속해서 나오지 않도록 조절하면 답을 $0$으로 출력할 수 있다. 즉, 0 사이사이에 다른 숫자를 끼워넣으면 된다는 것. 그러려먼 0의 개수가 배열의 반을 넘으면 안된다. 이것으로 $0$이 답인 것에 대한 핸들링을 끝낼 수 있다.
$0$이 답이 될 수 없다면, 즉 배열의 과반이 0이라면, 다음으로는 $1$이 답인 경우가 가장 이상적일 것이다. 아니라면 $2$가 가장 이상적. 이 때는 가능한 경우가 2가지로 나뉜다.
- 배열 안에 0과 1이 아닌 다른 수가 있는 경우 : 우리는 $a = [0, 0, 0, x, y, z, 1, 1, 1]$와 같은 경우로 배열을 만들 수 있고, 이 때 MEX 최솟값은 항상 $1$이다
- 배열 안에 0과 1밖에 없는 경우 : 어떻게든 0과 1이 만나는 지점이 존재한다. 그래서 1도 불가능. 다만 $2$ 이상을 만들 수는 없다. 0이 과반 이상 존재하기 때문. 따라서 MEX 최솟값은 $2$
이 때 예외상황이 존재한다. ‘배열의 모든 원소가 0인 경우’. 과반인 것을 넘어서 아예 모든 원소가 0인 경우는, 해보면 알겠지만 답이 $1$이어야한다. 이것만 핸들링해주면 된다.
막상 풀어보면 답이 $0$, $1$, $2$ 안에서만 나온다는 것을 알 수 있다. 배열을 아예 만들 필요가 없는 것. 생각해보면 0의 개수, 1의 개수, 배열의 길이만 있으면 모든 상황을 판단할 수 있게 된다. 위에서 bold체 되어있는 부분에서의 핸들링이 늦어서 B번 문제 제출까지 시간이 너무 오래 걸렸다. 심지어 한번 틀리기까지 했으니 순위 하락의 원인이 된 문제.
코드
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
#include <stdio.h>
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
int zeroCount = 0, oneCount = 0;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
int a;
scanf("%d", &a);
if (a == 0) {
++zeroCount;
} else if (a == 1) {
++oneCount;
}
}
if (zeroCount <= (n + 1) / 2) {
printf("0\n");
} else if (zeroCount + oneCount < n || zeroCount == n) {
printf("1\n");
} else {
printf("2\n");
}
}
return 0;
}
C. Sequence Master
풀이 보기
풀이
아까 B번 문제에서 종이 2장 썼다고 했었던가? 이 문제는 종이 4장을 쓸 동안 증명이 안되던 문제다. 값이 많아지면 많아질수록 연립해야할 변수가 많아지고, 그때마다 case 나누고… 이건 아니다 싶어서 갈아버리고 다시하고.. 시간 뺏는 역할인 것 같은 문제이다.
원소가 많아질수록 연립이 사실상 불가능하므로, 문제 이해를 돕기 위해 $n$이 작은 것부터 답을 찾아가며 연립해보자 했다. 원소가 $a$, $b$라면 문제 조건에 맞추기 위해서라면 당연하게도 $a = b$. $n$이 1일 때는 알아낼 정보가 딱히 없다.
그럼 다음, $n = 2$인 경우를 보자. 모든 원소를 $a, b, c, d$라고 하고 연립해보자.
\[ab = c + d, ac = b + d, ad = b + c\] \[bc = a + d, bd = a + c, cd = a + b\]이 때 $c$를 풀어내서 생각해보면 $ab - d = bd - a$. 이항시켜서 $b$로 묶어보면 $b(a - d) = -(a - d)$. 풀어보면 $a = d \text{ or } b = -1$. 두개 다 가능하므로 둘 다 해봐야 할 것 같다.
- $a = d, b \neq -1$인 경우, 아까 $c$를 제거했던 방법으로 $d$를 제거하면 $a = c$라는 값을 또 얻을 수 있다. 같은 방법으로 $a = d$라는 값도 얻을 수 있다. 이게 가능한 이유는, 원소의 순서가 상관 없이 어짜피 모든 원소가 모든 방법으로 연립식을 만들었기 때문. 원소의 순서를 바꾼다고 상황이 바뀌지 않는다. 당연하게도 이것은 $b$에도 적용되는 문제. 즉, 이 상황에서 만들어지는 상황은 $a = b = c = d \neq -1$이라는 것
- 모든 원소가 같은 값을 가지므로 가능한 것을 계산해보자. 모든 상황에서 $a^2 = 2a$가 되는 것을 알 수 있다. 이 때 가능한 값은 $a = 0 \text{ or } 2$. 다른 원소 모두 같은 값을 가진다
- $b = -1$이고, $a \neq d$인 경우, 첫 번째 식에 $b = -1$을 대입하면 $-a = c + d$이다. 그리고 위에서 했던 방법으로, $c$가 아닌 다른 원소로 풀어내서 연립해보면 $c = -1, d=-1$을 얻을 수 있다. 다만 $a$에는 그럴 수 없다. $a$와 $d$가 같지 않기 때문
- 그럼 나머지 원소가 전부 $-1$일 때 가능한 $a$값은 무엇일까? 그건 직접 하나의 식에 대입해보면 된다. $-1 \times -1 = -1 + a$이므로, $a$는 $2$다
위 상황을 토대로, $n = 2$라면 가능한 경우는 총 3가지다. $[0, 0, 0, 0], [-1, -1, -1, 2], [2, 2, 2, 2]$. 전부다 만들어보고 최솟값을 찾을 수 있을 것이다.
그럼 다음, $n=3$인 경우를 보자. 이 경우부터는 조금 생략해가면서 확인해보자 $e+f$에 대해서 연립해보면, $abc - d = abd - c$라는 결과를 얻을 수 있다. $ab$로 묶으면 $ab(c - d) = -(c - d)$이므로, $c=d$ or $ab = -1$이라는 결과를 얻을 수 있다.
- $c = d$라면, 아까와 같은 방법으로 $a = b = c = d$까지 얻을 수 있다. 더 가다보면 결국 모든 원소가 같은 경우 가능하다는 것까지 도달할 수 있다. 문제는 이 경우 가능한 $a$값이 될 것이다.
- 일단 $0$은 가능하다
- 0이 아니라면, $a^3 = 3a$를 풀어야 한다. $a$가 0이 아니므로 $a^2 = 3$. 정수로는 불가능하다. 아까 $n=2$일 때 $2$가 가능했던 것과는 대비되는 부분
- $ab = -1$인 경우, $a = -1, b=1$이라고 적을 수 있다. 같은 원리로 $c = -1, d=1$이 가능하다. 문제는 이 다음부터는 가능한 경우가 없다는 점
$n = 3$일 때 가능한 경우는 1개밖에 없었다. $[0, 0, 0, 0]$. $n$이 커져봤자 이 경우만 가능한 것인가? 근데 그렇다고 하기에는 예제에 있는 $n = 4$인 경우가 해결되지 않는다. 아직 찾지 못한 규칙이 있나보다. 그럼 해봐야겠지? 또 똑같이 연립해서 결과를 얻어보자. 그럼 $abc(d - e) = -(d - e)$를 얻을 수 있을 것이다. 그럼 또 $abc = -1$ or $d = e$겠다.
- $d = e$인 경우, 또또 모든 원소에 적용 가능하므로 $a^4 = 4a$를 계산해야한다. 물론 $a=0$ 말고는 불가능
- $abc = -1$인 경우, 전부 $-1$이거나 1개만 $-1$이고 나머지는 $1$인 경우가 가능할 것이다
- 1개만 $-1$인 경우, $n=3$에서 했던 결과를 토대로, 불가능한 조합이라는 결론에 도달한다.
- 모두가 $-1$인 경우, $n=2$에서 했던 결과를 토대로, 1가지 결론에 도달할 수 있다. 모든 원소가 $-1$이고, 하나의 원소가 4인 경우가 가능하다는 점
$n=4$인 경우 2가지가 가능하다는 것을 알 수 있다. $[0 \times 8], [-1 \times 7, 4]$. 예제는 후자의 배열을 토대로 결과값이 계산되었다는 것도 검증할 수 있었다.
$n = 5$인 경우도 똑같이 계산 가능하고, $abcd = -1$이라는 결론에 도달하였지만, 이 경우 또한 결과 도출이 불가능하다는 것을 알 수 있다. 이정도 계산을 하고보니, “원소에 1이 있으면 불가능한 경우“라는 것을 알아낼 수 있었다! 즉, $n$이 홀수라면 모든 원소가 0인 경우가 아니라면 1이 무조건 생기게되고, 그 경우는 불가능하다는 것.
$n$이 짝수라면 위 연립식에서 묶이는 모든 변수를 $-1$로 할 수 있으므로, 모든 원소가 0인 경우를 제외하고도 가능한 경우가 하나 더 생긴다. 결론을 적자면, 모든 원소가 $-1$이고, 하나의 원소가 $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
#include <stdio.h>
typedef long long ll;
#define MAX (ll)(2e9 + 1)
#define MAX_IDX (int)(2e5 + 10)
ll arr[MAX_IDX * 2];
int n;
#define abs(x) (((x) < 0) ? (-(x)) : (x))
#define min(a, b) (((a) > (b)) ? (b) : (a))
#define max(a, b) (((a) > (b)) ? (a) : (b))
int main() {
int t;
scanf("%d", &t);
while (t--) {
ll ret = 0;
ll max_value = -MAX;
scanf("%d", &n);
for (int i = 0; i < 2 * n; ++i) {
scanf("%lld", arr + i);
ret += abs(arr[i]);
max_value = max(max_value, arr[i]);
}
if (n == 1) {
ret = min(ret, abs(arr[0] - arr[1]));
}
if (n == 2) {
ll temp = 0;
for (int i = 0; i < 2 * n; ++i) {
temp += abs(2 - arr[i]);
}
ret = min(ret, temp);
}
if (n % 2 == 0) {
ll temp = 0;
int cnt = 0;
for (int i = 0; i < 2 * n; ++i) {
if (arr[i] == max_value) {
if (cnt++ > 0) {
temp += abs(-1 - arr[i]);
}
} else {
temp += abs(-1 - arr[i]);
}
}
temp += abs(n - max_value);
ret = min(ret, temp);
}
printf("%lld\n", ret);
}
return 0;
}
결과
| Contest | Start time | Rank | Solved | Rating change | New rating |
|---|---|---|---|---|---|
| #858 (Div. 2) | 2023/3/18 21:05 | 1387 | 3 | +71 | 1456 |
오랜만에 복귀한 것 치고 나름 잘 풀었다고 생각한다. B번 문제에서 생각을 좀 빨리 해봤다면 E번 문제를 손대보기라도 했을거 같은데, E번 문제가 심지어 브루트포스 문제라고 시간을 썼다면 운좋게 해결했을지도 모른다. 그랬다면 100점은 더 뛰었겠지..
그래도 복귀전이 이정도였으면 잘 했다고 생각한다. 다음 contest를 언제 참여할지는 모르겠지만, 다음에는 Expert 복귀를 목표로 할 것이다.