Codeforces Round #1042 (Div. 3) 후기
- Codeforces Round #1042 (Div. 3) 후기
A. Lever
풀이 보기
풀이
1번 연산이 몇번 진행되는지를 출력하라는 문제이다. 2번 연산은 페이크다!
1번 연산은 $a_i > b_i$인 수가 있다면 계속 반복하며, 없다면 종료한다. 그리고 연산은 $a_i$의 값을 $1$ 감소시키는 것이다. 즉, 특정 인덱스 $i$에 대해 $a_i > b_i$라면 1번 연산을 $a_i - b_i$번 수행해야한다. 결론적으로는 1번 연산은 아래 횟수만큼 진행될 것이다.
\(\sum_{i=1}^{n} \big( (a_i - b_i) \times (a_i > b_i) \big) + 1\) 마지막에 $1$을 추가하는 이유는, 문제에서 “연산이 무시될 때까지” 반복한다고 했으므로, 마지막 연산이 추가되어야해서다.
코드
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
#include <stdio.h>
#define MAX_IDX 10
int a[MAX_IDX];
int b[MAX_IDX];
int n;
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", a + i);
}
for (int i = 0; i < n; ++i) {
scanf("%d", b + i);
}
int ret = 0;
for (int i = 0; i < n; ++i) {
if (a[i] > b[i]) {
ret += (a[i] - b[i]);
}
}
printf("%d\n", ret + 1);
}
return 0;
}
B. Alternating Series
풀이 보기
풀이
조건 1에 의해, 인접한 두 원소의 부호는 반대여야한다. 조건 2에 의해, 양수인 부분이 음수인 부분보다 커야 한다.
그리고 전체 문제의 조건에 의해, 배열이 best하려면 첫 원소의 절댓값 $\vert a_1 \vert = 1$이어야 한다. 여기서 생각을 해보자.
- $a_1 = 1$이라면, $a_2 < 0$이면서 $\vert a_1 \vert > \vert a_2 \vert$이어야 하지만, 이를 만족하는 정수 $a_2$가 없다
- 즉, $a_1 = -1$이어야 한다. 이 때 $a_2 = 2$가 되어야 배열이 best일 수 있다. 하지만 그 다음을 생각해보자. $a_2 > 0$이었기 때문에 조건 1에 의해 $a_3 < 0$이어야하겠지? 그렇다면 조건 2의 $a_1 + a_2 + a_3 > 0$을 만족하는 $a_3$을 찾아야하는데, 정수 $a_3$이 없다!
- 결론적으로, $a_2 = 3$이어야하며, $a_3=-1$이면 된다.
최종적으로 배열은 $[-1, 3, -1, 3, -1, 3, \cdots]$가 반복되는 구조이어야한다! 하지만 끝부분에서 조금 갈라진다
- 배열의 길이가 홀수라면, $-1$이 마지막 값이 된다
- 배열의 길이가 짝수라면, 양수가 마지막 값이 된다. 이 때의 배열값은 $2$도 가능하다 (마지막 원소이기 때문에 조건 2를 위배하지 않는다)
여기까지 알아냈다면 그대로 출력만 해주면 된다.
코드
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
#include <stdio.h>
#define MAX_IDX (int)(2e5)
int n;
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
if (i % 2 == 0) {
printf("-1 ");
} else {
if (i == n-1) {
printf("2");
}else {
printf("3 ");
}
}
}
printf("\n");
}
return 0;
}
C. Make it Equal
풀이 보기
풀이
배열의 원소에 대해 우리가 할 수 있는 행동은 $+k$ 또는 $-k$뿐이다. 즉 어떤 수 $x$에 대해 $x - ret = Qk$가 성립한다.결론적으로는 $x$에 $k$로 모듈러를 취한 결과를 얻어낼 수 있다. 이 때 절댓값이 있었으므로, $x$는 $x \mod k$ 또는 $k - m \mod k$가 될 수 있다.
이 때 $S$와 $T$가 서로 같은 set이 될 수 있는지 확인하면 된다. 즉 $S$의 원소들을 모듈러 취해준 다음, 이 값들에 $k$를 계속 적절히 더해서 $T$로 만들 수 있는지 확인해야한다. $T$의 원소들도 모듈러를 취해주면 $S$와 $T$의 비교를 쉽게 할 수 있을 것이다.
코드
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
#include <bits/stdc++.h>
using namespace std;
static inline long long norm_mod(long long x, long long k) {
long long r = x % k;
if (r < 0) r += k;
return r;
}
static inline long long bucket_of(long long x, long long k) {
long long r = norm_mod(x, k);
return min(r, k - r);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
if (!(cin >> t)) return 0;
while (t--) {
int n; long long k;
cin >> n >> k;
if (k <= 0) {
long long tmp;
for (int i = 0; i < n; ++i) cin >> tmp;
for (int i = 0; i < n; ++i) cin >> tmp;
cout << "NO\n";
continue;
}
vector<long long> A; A.reserve(n);
vector<long long> B; B.reserve(n);
for (int i = 0; i < n; ++i) {
long long x; cin >> x;
A.push_back(bucket_of(x, k));
}
for (int i = 0; i < n; ++i) {
long long x; cin >> x;
B.push_back(bucket_of(x, k));
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
cout << (A == B ? "YES" : "NO") << '\n';
}
return 0;
}
D. Arboris Contractio
풀이 보기
풀이
문제에서 원하는 지름은 최대 $2$가 된다는 것은 문제를 자세히 이해하면 알 수 있게 된다. 어떤 정점 $v$를 정하고, 모든 다른 정점들이 $v$와 단일 연결되도록 연산을 무한히 실행할 수 있기 때문이다. 그렇게 되면 모든 정점들은 $s \rightarrow v \rightarrow t$로 연결되기 때문에, 지름은 $2$가 된다. 물론 정점이 원래 $2$개였다면 지름은 $1$이 될 것이다. (문제풀때는 생각하지 않아도 된다)
결국 정점 $v$에 대해 최종 형태는 정해져있다. 이 때 연산 횟수를 최소화하기 위해서는, “처음부터 자신과 직접 연결된 정점이 가장 많은” 정점 $v$를 선택해야한다. 연산을 1번 수행할 때마다 리프 정점들이 계속 $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
#include <stdio.h>
#include <string.h>
#define MAXN 200000
static int deg[MAXN + 5];
static int leafNbr[MAXN + 5];
static int U[MAXN + 5], V[MAXN + 5];
int main(void) {
int t;
if (scanf("%d", &t) != 1) return 0;
while (t--) {
int n;
scanf("%d", &n);
// reset only needed range
memset(deg, 0, (n + 2) * sizeof(int));
memset(leafNbr, 0, (n + 2) * sizeof(int));
for (int i = 1; i <= n - 1; ++i) {
int u, v;
scanf("%d %d", &u, &v);
U[i] = u; V[i] = v;
deg[u]++; deg[v]++;
}
if (n == 2) {
printf("0\n");
continue;
}
int L = 0;
for (int i = 1; i <= n; ++i) if (deg[i] == 1) L++;
for (int i = 1; i <= n - 1; ++i) {
int u = U[i], v = V[i];
if (deg[u] == 1) leafNbr[v]++;
if (deg[v] == 1) leafNbr[u]++;
}
int mx = 0;
for (int i = 1; i <= n; ++i) if (leafNbr[i] > mx) mx = leafNbr[i];
int ans = L - mx;
printf("%d\n", ans);
}
return 0;
}
E. Adjacent XOR
풀이 보기
풀이
모든 인덱스에 대해 연산을 최대 1번 수행할 수 있다는 점을 기억하자. 또, $a_i$의 값은 $a_i$와 $a_{i+1}$를 $\oplus$한 값이 될 수 있다. 즉, 마지막 원소인 $a_n$은 그 뒤가 없기 때문에 값이 변경되지 않는다. 즉, 마지막 원소들이 고정되면 그 전 원소들의 값도 그걸로 정해진다는 것을 의미한다. 뒤에서부터 연산해나가면 된다는 뜻.
우리는 $a$ 배열을 $b$와 똑같이 만드는 것이 목표이다. 아래와 같은 과정으로 진행하면 된다.
- 마지막 원소 $a_n$은 $b_n$과 같아야한다. 다르다면 배열을 같게 만들 수 없다
- 다른 원소들에 대해, 뒤에서부터 연산을 고려한다
- $a_i = b_i$라면 연산하지 않아도 된다
- $a_i \oplus a_{i+1} = b_i$라면 연산하면 된다
- $a_i \oplus b_{i+1} = b_i$라면, 뒤에 연산 이전에 $i$번에서 연산을 먼저 수행해야한다. 이 부분이 문제를 더 까다롭게하는 부분이었다
- 그 이외에는 배열을 같게 만들기가 불가능하다
코드
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
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
#define MAX_IDX (int)(2e5)
int a[MAX_IDX];
int b[MAX_IDX];
int n;
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", a + i);
}
for (int i = 0; i < n; ++i) {
scanf("%d", b + i);
}
bool result = true;
if (a[n - 1] != b[n - 1]) {
result = false;
} else {
for (int i = n - 1; i > 0; --i) {
if ((a[i - 1] != b[i - 1]) && (((a[i - 1] ^ b[i]) != b[i - 1]) && ((a[i - 1] ^ a[i]) != b[i - 1]))) {
result = false;
break;
}
}
}
printf("%s\n", (result == true) ? "YES" : "NO");
}
return 0;
}
결과
| Contest | Start time | Rank | Solved | Rating change | New rating |
|---|---|---|---|---|---|
| #1042 (Div. 3) | 2025/8/10 23:35 | 1724 | 5 | +33 | 1495 |