Educational Codeforces Round 120 (Rated for Div. 2)

12/28 추가)

어림도 없지!!!! C번 시스텟에서 터져버리기 ㅋㅋ 그래.. 그래도 점수는 올랐으니까~

오늘 또 코포가 있던데, 오늘도 보아야겠다.

C번 업솔빙도 오늘 할 예정.

ㅎㅇㅌ ㅎㅇㅌ

 

---

기존글

 

 

최근 div2는 2솔만 하다가 오늘 3솔해서 기분이 좋다!

 

민트 퍼포가 나왔다. C번에서 한 줄 때문에 1시간이나 날린 점은 매우 아쉽지만... ㅠㅠ

근데 이거 저 38점오르나요 49점 오르나요...? 아시는 분 댓글 부탁드립니다ㅠ

후자가 맞다면 오늘 민트를 찍는다!

 

 

A.

정수 세 개가 주어지고, 하나의 정수를 쪼개서 총 4개의 정수를 각 변으로 하는 직사각형을 만들 수 있는지 묻는 문제이다. 정수를 쪼갤 때 정수들로만 쪼갤 수 있다는 것을 놓쳐서 5분이나 써버렸다.

 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

vector<ll> vec(3);

void solve() {
	cin >> vec[0] >> vec[1] >> vec[2];
	sort(vec.begin(), vec.end(), greater<>());
	ll a = vec[0], b = vec[1], c = vec[2];
	if (a == b + c) cout << "YES" << endl;
	else {
		if (a == b && c % 2 == 0) cout << "YES" << endl;
		else if (b == c && a % 2 == 0) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
}


int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int tc = 1; cin >> tc;
	while (tc--) {
		solve();
	}

	return 0;
}

 

 

 

B.

이 문제 이해하는 데 시간이 많이 들었다. 분명 좋아하는 노래의 순위가 더 높아야 한댔는데, 예제들은 반대였다. 알고보니 순위가 아니라 레이팅이었다. 클수록 좋은 것... 좋아하는 노래와 싫어하는 노래를 각각 정렬하여 순서대로 레이팅을 부여했다. 

 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

ll n;
ll arr[200001];
ll rating[200001];
string s;

void solve() {
	cin >> n;
	for (ll i = 0; i < n; i++) cin >> arr[i];
	vector<pair<ll, ll>> vec;
	cin >> s;
	vector<pair<ll,ll>> like;
	vector<pair<ll, ll>> dislike;
	for (ll i = 0; i < s.size(); i++) {
		if (s[i] == '0') {
			dislike.push_back({ arr[i],i });
		}
		else like.push_back({ arr[i],i });
	}
	sort(like.begin(), like.end());
	sort(dislike.begin(), dislike.end());
	for (ll i = 0; i < dislike.size(); i++) {
		rating[dislike[i].second] = i + 1;
	}
	for (ll i = 0; i < like.size(); i++) {
		rating[like[i].second] = dislike.size() + i + 1;
	}
	for (ll i = 0; i < n; i++) {
		cout << rating[i] << ' ';
	}
	cout << endl;
}


int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int tc = 1; cin >> tc;
	while (tc--) {
		solve();
	}

	return 0;
}

 

 

 

C.

첫 제출 후 50분 만에 맞췄다....ㅠㅠ 패널티도 많이 쌓였다.

 

처음에는 파라메트릭 서치 느낌이 확 났는데, 정확히 어떻게 구현해야 할지 모르겠어서 다른 방향으로 생각해보았다.

 

그리디하게 문제에 접근했다. 우선 정렬을 한 뒤, 가장 작은 원소를 작게 줄인 다음, 큰 값들을 가장 작은 원소의 값으로 변경하는 식으로 코드를 작성하였다. 가장 작은 원소를 얼마나 줄일 지는 잘 모르겠어서 k/n부터 점점 줄여가면서 전부 다 확인해보는 식으로 접근하였다.

 

답이 최소가 지나는 지점을 지나면 다시 증가하는 성질을 알게 되었다. (최고차항이 양수인 2차함수 처럼..)

 

근데 5번이나 틀리더라 ㅠ 결국 마지막에 k/n보다 수열의 최소값이 더 작은 경우도 있다는 것을 발견해서 코드 한 줄 추가하고 맞았다. 아, 그리고 사실 TLE가 날 줄 알았는데 안나더라... 정확한 시간복잡도는 잘 모르겠다 ㅠ 맞 왜 맞?

 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

ll n, k;

void solve() {
	cin >> n >> k;
	vector<ll> arr(n);
	ll sum = 0;
	for (ll i = 0; i < n; i++) {
		cin >> arr[i];
		sum += arr[i];
	}
	if (sum <= k) {
		cout << 0 << endl;
		return;
	}
	sort(arr.begin(), arr.end());
	ll high = k / n;
	high = min(high, arr[0]);
	ll low = -1;
	ll ans = 9223372036854775807;
	while (1) {
		ll tmp = arr[0] - high;
		ll cnt = arr[0] - high;
		ll idx = n - 1;
		while (k < sum - tmp) {
			cnt++;
			if (arr[idx] - high == 0) cnt--;
			tmp += arr[idx] - high;
			idx--;
		}
		if (cnt > ans) break;
		ans = min(ans, cnt);
		high--;
	}

	cout << ans << endl;
}


int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int tc = 1; cin >> tc;
	while (tc--) {
		solve();
	}

	return 0;
}

 

 

---

 

그린 색깔이 너무 안 이뻤는데, 드디어 민트에 갈 수 있는건가?! 갔으면 좋겠다.