[Codeforces] Round #552 (Div. 3) A ~ E 풀이

 

21.01.11 12:30 virtual 참가 (1시간 20분) / performance = 1816

 

 

 

A. Restoring Three Numbers  (*800)

 

입력으로 a+b, a+c, b+c, a+b+c가 랜덤 순서로 들어온다. 

이를 다 더하면 3(a+b+c) 이므로, a+b+c의 값을 구해줄 수 있다. 

따라서 구한 a+b+c의 값과 동일한 입력을 찾은 뒤, 해당 입력에서 나머지 세 입력을 빼주면 각각 a,b,c가 나온다. 

 

[소스 코드]

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
		ll a, b, c, d; cin >> a >> b >> c >> d;
		ll total = a + b + c + d;
		total /= 3;
		if (a == total) {
			cout << a - b << ' ' << a - c << ' ' << a - d;
		}
		else if (b == total) {
			cout << b - a << ' ' << b - c << ' ' << b - d;
		}
		else if (c == total) {
			cout << c - a << ' ' << c - b << ' ' << c - d;
		}
		else cout << d - a << ' ' << d - b << ' ' << d - c;
	
}

 

 

B. Make Them Equal (*1200)

 

어떤 음이 아닌 정수 D로 배열의 각 원소를 더하거나, 빼거나, 그대로 둘 때 모든 원소를 동일하게 만들 수 있다면 그 가능한 D중 최솟값을 찾는 문제이다. 

배열의 원소들의 범위가 작으므로 완전탐색으로 배열의 원소가 k로 같다면 이를 만들 수 있는 D가 존재하는지를 찾는다. 

 

[소스 코드]

#include<bits/stdc++.h>
#define ini(x, y) memset(x, y, sizeof(x));
using namespace std;

int A[101];
int cnt[301];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n; cin >> n;
	int ans = 100000;
	for (int i = 1; i <= n; i++) cin >> A[i];
	for (int i = -100; i <= 200; i++) {
		ini(cnt, 0);
		for (int j = 1; j <= n; j++) {
			cnt[abs(A[j] - i)]++;
		}
		int k = 0;
		for (int i = 1; i <= 300; i++) {
			if (cnt[i] > 0) k++;
		}
		if (k <= 1) {
			int tmp = 0;
			for (int j = 1; j <= n; j++) {
				tmp = max(tmp, abs(A[j] - i));
			}
			ans = min(ans, tmp);
		}
	}
	if (ans == 100000) cout << -1;
	else cout << ans;
}

 

 

C. Gourmet Cat (*1400)

 

월/목/일요일에는 fish를, 화/토요일에는 rabbit을, 수/금요일에는 chicken을 먹고, 

fish는 a개, rabbit은 b개, chicken은 c개 있을 때, 가장 오래 먹을 수 있도록 요일을 고르는 문제이다. 

어떤 요일부터 시작하든, 항상 7일동안은 fish를 3개, rabbit과 chicken을 2개씩 먹는다. 

따라서 최소 min(a/3, b/2, c/2) * 7일 만큼은 먹을 수 있고, 나머지를 가지고 얼마나 더 먹을 수 있는지 확인한다.

a, b, c중 적어도 하나는 1이하의 값이 되므로 직접 다 돌려보면 된다.

 

[소스 코드]

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int A[7] = { 1, 2, 3, 1, 3, 2, 1 };
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	ll a, b, c; cin >> a >> b >> c;
	ll ans = 0;
	ll k = min({ a / 3, b / 2, c / 2 });
	a -= k * 3;
	b -= k * 2;
	c -= k * 2;
	for (int i = 0; i < 7; i++) {
		ll ta = a;
		ll tb = b;
		ll tc = c;
		ll cnt = 0;
		for (int j = i; ; j++) {
			if (A[j % 7] == 1) {
				if (ta == 0) break;
				else cnt++, ta--;
			}
			else if (A[j % 7] == 2) {
				if (tb == 0) break;
				else cnt++, tb--;
			}
			else {
				if (tc == 0) break;
				else cnt++, tc--;
			}
		}
		ans = max(ans, k * 7 + cnt);
	}
	cout << ans;
}

 

 

D. Walking Robot (*1500)

 

battery와 accumulator의 최대 용량이 각각 b, a이고, 시작할 때는 최대만큼 채워져있다.

1인 구간을 지나갈 때에 만약 battery를 이용한다면 accumulator의 용량은 1 증가한다. 최대 용량을 넘지는 못한다.

0인 구간은 감소하기만 한다. 

 

따라서, 1인 구간을 지나갈 때, accumulator의 용량이 꽉차있지 않고 battery를 이용할 수 있다면 무조건 battery를 이용하는게 이득이고, 0인 구간을 지나갈 땐 최대한 accumulator를 이용하는게 이득이다.

 

[소스 코드]

#include<bits/stdc++.h>
using namespace std;
int s[200001];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n, b, a; cin >> n >> b >> a;
	int nowa = a;
	int nowb = b;
	for (int i = 1; i <= n; i++) cin >> s[i];
	for (int i = 1; i <= n; i++) {
		if (s[i] == 1) {
			if (nowb > 0) {
				if (nowa == a) 	nowa--;
				else {
					nowb--;
					nowa++;
				}
			}
			else if (nowa > 0) nowa--;
			else return cout << i - 1, 0;
		}
		else {
			if (nowa > 0) nowa--;
			else if (nowb > 0) nowb--;
			else return cout << i - 1, 0;
		}
	}
	cout << n;
}

 

 

E. Two Teams (*1800)

 

두 코치가 서로 번갈아가면서 선수들을 뽑아가는데, 현재 남은 선수 중 제일 높은 선수를 뽑는다.

그리고 그 선수 양옆으로 남은 선수들 중 각각 k명씩 데리고 간다. 만약 k명이 없다면 있는 만큼만 뽑아간다.

 

먼저, 선수들의 능력치와 위치를 priority_queue에 저장하여 매번 제일 높은 선수를 확인하도록 한다. 

그리고, 현재 선수를 기준으로 왼쪽에 있는 선수와 오른쪽에 있는 선수를 저장해두고, 선수를 뽑아갈 때마다 

좌우의 선수를 갱신시켜준다. 

 

[소스 코드]

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int L[200010], R[200010];
int A[200010];
int ans[200010];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n, k; cin >> n >> k;
	priority_queue<pii> pq;
	for (int i = 1; i <= n; i++) {
		L[i] = i - 1;
		R[i] = i + 1;
		cin >> A[i];
		pq.push({ A[i], i });
	}
	R[n + 1] = n + 1;
	int turn = 1;
	while (!pq.empty()) {
		pii p = pq.top(); pq.pop();
		if (A[p.second] == -1) continue;
		ans[p.second] = turn;
		A[p.second] = -1;
		vector<int> tmp;
		int cnt = 0;
		int idx = p.second;
		while (1) {
			idx = L[idx];
			if (idx == 0) break;
			tmp.push_back(idx);
			if (A[idx] == -1) continue;
			else {
				A[idx] = -1;
				ans[idx] = turn;
				cnt++;
			}
			if (cnt == k || idx == 0) break;
		}
		idx = L[idx];
		for (int i : tmp) L[i] = idx;
		tmp.clear();
		cnt = 0;
		idx = p.second;
		while (1) {
			idx = R[idx];
			if (idx == n + 1) break;
			tmp.push_back(idx);
			if (A[idx] == -1) continue;
			else {
				A[idx] = -1;
				ans[idx] = turn;
				cnt++;
			}
			if (cnt == k || idx == n + 1) break;
		}
		idx = R[idx];
		for (int i : tmp) R[i] = idx;
		if (turn == 1) turn = 2;
		else turn = 1;
	}
	for (int i = 1; i <= n; i++) cout << ans[i];
}

 

이 문제를 set으로도 풀 수 있다. 

set이 자동으로 정렬해주므로, 굳이 양쪽의 원소가 무엇인지 갱신시켜줄 필요가 없다.

set의 유용성을 많이 느끼게 해주는 문제이다. 

 

[소스 코드]

#include<bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
int ans[200001];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n, k; cin >> n >> k;
	set<int> s;
	priority_queue<pii> pq;
	for (int i = 1; i <= n; i++) {
		int a; cin >> a;
		s.insert(i);
		pq.push({ a, i });
	}
	int turn = 1;
	while (!pq.empty()) {
		pii p = pq.top(); pq.pop();
		auto it = s.lower_bound(p.second);
		if (it == s.end() || *it != p.second) continue;
		ans[p.second] = turn;
		s.erase(it);
		for (int i = 1; i <= k; i++) {
			auto left = s.lower_bound(p.second);
			if (left == s.begin()) break;
			left--;
			ans[*left] = turn;
			s.erase(left);
		}
		for (int i = 1; i <= k; i++) {
			auto right = s.lower_bound(p.second);
			if (right == s.end()) break;
			ans[*right] = turn;
			s.erase(right);
		}
		if (turn == 1) turn = 2;
		else turn = 1;
	}
	for (int i = 1; i <= n; i++) cout << ans[i];
}