Atto Round 1 (Codeforces Round 1041, Div. 1 + Div. 2) 후기
- Atto Round 1 (Codeforces Round 1041, Div. 1 + Div. 2) 후기
A. Mix Mex Max
풀이 보기
풀이
조건을 나누어 하나씩 생각해보자.
- $0$이 배열 안에 존재한다 : $MIN = 0$이 된다. 즉 $MEX = MAX$
- case work를 해보면 알겠지만, $MEX$와 $MAX$는 같을 수 없다. 즉 $0$이 배열에 있다면 불가능한 경우
- 결국 $0$이 없기 때문에 항상 $MEX=0$이 된다. 즉 $MAX = MIN$이어야 한다
결론적으로, $MAX=MIN$이기 위해서는 배열에 모두 $0$이 아닌 같은 수로만 채워져있어야 한다!
코드
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
#include <stdio.h>
int main() {
int T;
if (scanf("%d", &T) != 1) return 0;
while (T--) {
int n;
scanf("%d", &n);
int v = -1;
int ok = 1;
for (int i = 0; i < n; i++) {
int a;
scanf("%d", &a);
if (a != -1) {
if (a == 0) {
ok = 0;
} else if (v == -1) {
v = a;
} else if (a != v) {
ok = 0;
}
}
}
puts(ok ? "YES" : "NO");
}
return 0;
}
B. Hamiiid, Haaamid… Hamid?
풀이 보기
풀이
Hamid는 항상 같은 방향으로만 진행하는게 이득이다. Mani는 그럼 Hamid를 최대한 막으려고 한다.
Hamid의 입장에서 생각해보자. 왼쪽에 벽 3개, 오른쪽에 벽 1개가 있다면 오른쪽으로 이동하는 것이 최선일 것이다. 그렇다면 Mani는 오른쪽에 벽을 설치하는 것이 최선의 전략이 된다.
Mani가 벽을 먼저 설치한다는 것을 생각하자. 벽이 설치된 후 Hamid가 최선의 선택을 하게 된다. 이 때 최선의 선택은 도착지점에 더 가까운 방향이 될 것이다. 벽을 제외하고 더 가까운 쪽을 선택하는 이유는, 이후부터 Mani가 그 방향으로 계속 벽을 설치할 수 있기 때문에, 걸리는 시간이 거리와 같아지기 때문이다.
하지만, Mani가 벽을 처음에 하나만 설치할 수 있기 때문에, 처음 단계에서는 Hamid가 왼쪽 또는 오른쪽으로 벽이 없는 곳까지 이동 가능하다는 점이다. 이정도 고려해서 개수를 세면 답을 얻을 수 있다.
코드
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
#include <stdio.h>
#define MAX_IDX (int)(2e5 + 1)
const int NONE = -1;
char grid[MAX_IDX + 1];
int n;
int x;
const int WALL = '#';
const int EMPTY = '.';
#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--) {
scanf("%d %d", &n, &x);
--x;
scanf("%s", grid);
// left
int first_left = -1;
int left_empty = 0;
for (int i = 0; i < x; ++i) {
if (grid[i] == WALL) {
first_left = i;
} else {
++left_empty;
}
}
// right
int first_right = n;
int right_empty = 0;
for (int i = n - 1; i > x; --i) {
if (grid[i] == WALL) {
first_right = i;
} else {
++right_empty;
}
}
// first case
if (first_left == NONE && first_right == NONE) {
printf("1\n");
} else {
int left_ret = 1;
int right_ret = 1;
// left place
if (left_empty > 0) {
left_ret = min(x, (n - first_right)) + 1;
} else {
left_ret = min(x, (n - x - 1)) + 1;
}
// right place
if (right_empty > 0) {
right_ret = min(first_left + 1, (n - x - 1)) + 1;
} else {
right_ret = min(x, (n - x - 1)) + 1;
}
// cmp
int ret = max(left_ret, right_ret);
printf("%d\n", ret);
}
}
return 0;
}
C. Trip Shopping
풀이 보기
풀이
두 배열 $a, b$가 있을 때, 선택한 인덱스 $i, j$에 대해서 4개의 값을 임의배치하여 각 플레이어들이 원하는 결과를 얻도록 하는 문제이다. 우리는 Ali의 관점이며, 점수 $v$를 최소화하는 것이 목표이다.
Bahamin의 목표가 선택된 인덱스에 대해 $v$의 최대화이다. 이 때 Bahamin은 목표를 위해 배열을 변경하거나 가만히 둘 수도 있다. 이 때 $v$는 항상 커지거나 같다. 작아지지 않는다.
Ali의 입장에서 생각해보자. 인덱스를 선택한다는 것은 $v$가 커지는 위험을 항상 동반하는 꼴이다. 이 과정을 총 $k$번 진행해야한다. 어떤 방법이 Ali의 입장에서 최선의 인덱스 선택일까? 정답은 $v$의 증가를 최소화하는 인덱스를 계속 선택하는 것이다. Bahamin은 $v$를 최대화하도록 배열을 변경할 것이지만, 이후부터는 계속 배열을 그대로 두어야 한다. 이미 최적의 상황으로 맞춰두었기 때문. 즉, $k$번의 라운드를 진행하는 것이 의미가 없다!
결국 Ali가 “$v$가 증가를 최소로 하는” 인덱스 $i, j$를 찾는 과정 1번만 필요하다는 것이다. 다만 수의 범위 때문에 완전탐색으로는 찾을 수 없다. 여기서 찾은 방법이 $a+b$가 제일 작은 친구들 위주로 선택하는 것. 그러면 같은 순서더라도 숫자들이 작은 애들이 더 유리하다는 것은 자명하다. 여기서 $v$의 증가량을 계산하고, 그들 중 제일 작은 인덱스를 추려내면 된다.
코드
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
#include <stdio.h>
#include <stdlib.h>
typedef long long ll;
#define MAX_IDX (int)(2e5)
const ll INF = (ll)987654321987654321;
ll a[MAX_IDX];
ll b[MAX_IDX];
ll vpair[MAX_IDX];
int n, k;
ll absll(ll x) {
return (x < 0) ? -x : x;
}
typedef struct {
ll a, b;
ll vdiff;
} Pair;
Pair p[MAX_IDX];
ll read_input() {
ll v = 0;
scanf("%d %d", &n, &k);
for (int i = 0; i < n; ++i)
scanf("%lld", &a[i]);
for (int i = 0; i < n; ++i) {
scanf("%lld", &b[i]);
vpair[i] = absll(a[i] - b[i]);
v += vpair[i];
p[i].a = a[i];
p[i].b = b[i];
p[i].vdiff = vpair[i];
}
return v;
}
ll max_permuted_cost(ll x1, ll x2, ll x3, ll x4) {
ll vals[4] = {x1, x2, x3, x4};
for (int i = 3; i > 0; --i)
for (int j = 0; j < i; ++j)
if (vals[j] > vals[j + 1]) {
ll tmp = vals[j];
vals[j] = vals[j + 1];
vals[j + 1] = tmp;
}
return (vals[3] - vals[0]) + (vals[2] - vals[1]);
}
int cmp(const void* x, const void* y) {
const Pair* px = (const Pair*)x;
const Pair* py = (const Pair*)y;
ll sum_x = px->a + px->b;
ll sum_y = py->a + py->b;
return (sum_x > sum_y) - (sum_x < sum_y);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
ll v = read_input();
qsort(p, n, sizeof(Pair), cmp);
ll min_delta = INF;
for (int i = 0; i < n - 1; ++i) {
ll cur_v = absll(p[i].a - p[i].b) + absll(p[i + 1].a - p[i + 1].b);
ll new_v = max_permuted_cost(p[i].a, p[i + 1].a, p[i].b, p[i + 1].b);
if (new_v - cur_v < min_delta)
min_delta = new_v - cur_v;
}
printf("%lld\n", v + min_delta);
}
return 0;
}
결과
| Contest | Start time | Rank | Solved | Rating change | New rating |
|---|---|---|---|---|---|
| #1041 (Div. 1 + Div. 2) | 2025/8/7 23:35 | 4850 | 3 | -19 | 1462 |