[Codeforces] Educational Round 76 (A ~ E) 풀이

 

2021.01.01 23:00 virtual 참가 / Performance = 1841

 

 

 

[풀이]

 

1257A. Two Rival Students

 

수직선상에 두 사람이 서있고, 한번 작업을 수행하면 두 사람의 거리를 1만큼 더 멀게 할 수 있다. 

최대 x번 작업을 수행할 수 있으므로, 멀어질 수 있을 만큼 최대한 이동시켜준다.

 

int main(void) {
	int T; cin >> T;
	while (T--) {
		int n, x, a, b; cin >> n >> x >> a >> b;
		if (a > b) swap(a, b);
		cout << min(n-1, b - a + x) << '\n';
	}
}

 

1257B. Magic Stick

 

x가 y보다 크거나 같으면 항상 -1씩 줄여나가면 y를 만들 수 있다.

x가 y보다 작은 경우 중에서는, x = 2이고 y = 3인 경우에 가능하다.

또 x가 4 이상인 경우에는 x를 무한히 키울 수 있기 때문에 항상 가능하다. 

 

int main(void) {
	int T; cin >> T;
	while (T--) {
		int x, y; cin >> x >> y;
		if (x >= y) cout << "YES\n";
		else {
			if (x == 2 && y == 3) cout << "YES\n";
			else if (x >= 4) cout << "YES\n";
			else cout << "NO\n";
		}
	}
}

 

1257C. Dominated Subarray

 

어떤 원소 v에 대해서 dominated 되면서 배열의 길이가 가장 짧기 위해서는 subarray의 양 끝에 v가 있고, 그 사이에는 모두 서로 다른 원소가 존재하는 경우이다. 

만약 양 끝에 v가 아니라면 끝의 원소를 없애도 dominated가 유지되기 때문이다. 

따라서 이를 투 포인터로 2번 나오는 원소가 나올 때마다 답을 갱신해준다.

 

int A[200001];
int main(void) {
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		vector<int> cnt(n + 1);
		int ans = MAX;
		for (int i = 1; i <= n; i++) cin >> A[i];
		int s = 1;
		for (int i = 1; i <= n; i++) {
			cnt[A[i]]++;
			if (cnt[A[i]] == 2) {
				while (A[s] != A[i]) {
					cnt[A[s]]--;
					s++;
				}
				ans = min(ans, i - s + 1);
				cnt[A[s]]--;
				s++;
			}
		}
		if (ans == MAX) cout << -1 << '\n';
		else cout << ans << '\n';
	}
}

 

1257D. Yet Another Monster Killing Problem

 

몬스터를 하루 할당량만큼 다 죽이거나, 혹은 더 높은 파워의 몬스터가 있어 던전을 빠져나오는 경우에만

하루가 끝나기 때문에 최대한 오래 싸울 수 있는 영웅을 고르는 것이 최적이다. 

 

따라서 endurance 마다 가질 수 있는 영웅의 최대의 power를 저장해 두고,

[a, b] 구간의 몬스터를 잡을 수 있는 경우에는 mx[b-a+1]의 값이 [a, b] 구간의 몬스터의 power의 최대 이상이 되어야 한다.

이를 만족하는 최대 길이의 구간을 계속해서 구해나가는 것이 핵심이다.

#include<bits/stdc++.h>
using namespace std;
int a[200001];
int mx[200001];
int main(void) {
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i]; mx[i] = 0;
		}
		int m; cin >> m;
		for (int i = 1; i <= m; i++) {
			int p, s; cin >> p >> s;
			mx[s] = max(mx[s], p);
		}
		for (int i = n; i >= 1; i--) {
			mx[i - 1] = max(mx[i], mx[i - 1]);
		}
		int i = 1;
		int len = 1;
		int ans = 1;
		int k = 0;
		while (i <= n) {
			k = max(k, a[i]);
			if (mx[len] < k) {
				if (len == 1) {
					ans = -1;
					break;
				}
				ans++;
				len = 1;
				k = 0;
			}
			else {
				len++;
				i++;
			}
		}
		cout << ans << '\n';
	}
}

 

1257E. The Contest

 

1, 2, 3으로 이루어진 수열이 주어질 때, 1....12....23...3 과 같이 만들어주기 위한 최소 변경 횟수를 구하는 문제이다.

즉, 같은 숫자끼리는 항상 이웃해야 하고 오름차순을 만족해야 한다는 의미이다.

여기서 반드시 1,2,3이 모두 나올 필요는 없다.

 

dp[i][j] = A[i] = j이면서 문제 조건을 만족하는 i번째 원소까지의 최소 변경 횟수라고 하면, 

dp[i][1]은 앞에 항상 1이 와야 하므로 dp[i-1][1]을 가져오고, 

dp[i][2]는 앞에 1 또는 2가 올 수 있으므로 dp[i-1][1], dp[i-1][2]를 가져오고,

dp[i][3]은 앞에 어떤 수가 와도 상관없으므로 dp[i-1][1], dp[i-1][2], dp[i-1][3] 모두 가져온다.

 

#include<bits/stdc++.h>
using namespace std;
const int MAX = (int)2e9;

int num[200001];
int dp[200001][4];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int k1, k2, k3; cin >> k1 >> k2 >> k3;
	int n = k1 + k2 + k3;
	for (int i = 1; i <= k1; i++) {
		int a; cin >> a;
		num[a] = 1;
	}
	for (int i = 1; i <= k2; i++) {
		int a; cin >> a;
		num[a] = 2;
	}
	for (int i = 1; i <= k3; i++) {
		int a; cin >> a;
		num[a] = 3;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 3; j++) {
			dp[i][j] = MAX;
			for (int k = 1; k <= j; k++) {
				dp[i][j] = min(dp[i][j], dp[i - 1][k] + (j != num[i] ? 1 : 0));
			}
		}
	}
	cout << min({ dp[n][1], dp[n][2], dp[n][3] });
}