Educational Codeforces Round 120 (Rated for Div. 2) 1654 -> 1634

Dashboard - Educational Codeforces Round 120 (Rated for Div. 2) - Codeforces

Dashboard - Educational Codeforces Round 120 (Rated for Div. 2) - Codeforces

!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!

 

 

A. Construct a Rectangle

Problem - A - Codeforces

Problem - A - Codeforces

문제

 

3개의 양의 정수가 주어진다. 하나를 골라 원하는 길이의 2개 수로 나눌 수 있는데, 최종적으로 만들어진 4개의 수로 직사각형을 만들 수 있으면 YES 아니면 NO를 출력하는 문제

 

풀이

 

3개를 받아 정렬 후, 큰 값 2개가 같다면 작은 값 1개가 짝수여야만 하고, 작은값 2개가 같다면 큰 값 1개가 짝수여야만 한다 , 이외에는 작은 값2개 더한 값이 큰값이라면 YES 아니면 NO를 출력하면 된다.

 

 

코드

 

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		long long a[3];
		for (int i = 0; i < 3; i++)cin >> a[i];
		sort(a, a + 3);
		if (a[2] == a[1]) {
			if (a[0] % 2)cout << "NO\n";
			else cout << "YES\n";
			continue;
		}
		if (a[0] == a[1]) {
			if (a[2] % 2)cout << "NO\n";
			else cout << "YES\n";
			continue;
		}
		if ((a[0] + a[1]) == a[2])cout << "YES\n";
		else cout << "NO\n";
	}
 
}

 

 

B. Berland Music

Problem - B - Codeforces

Problem - B - Codeforces

 

문제

 

n개의 곡이 있는데 각 곡들에는 예측 레이팅이 있다. 그리고 각 곡마다 좋아요와 싫어요 버튼이 있는데 좋아요를 받았으면 1, 싫어요라면 0 으로 입력이 주어진다. 이때 각 새로 레이팅을 매겨야하는데 조건이 1. 레이팅은 permutation이고,  2. 좋아요 받은 곡이 싫어요 받은 곡보다 레이팅이 높아야 한다. 라는 조건에 맞게 레이팅을 새로 조정할 때, 예측 레이팅과 새로 만들어진 레이팅들의 차이의 절대값 합들이 최소가 되게 레이팅을 새로 출력하는 문제

 

풀이

 

싫어요 , 좋아요 받은 인덱스끼리 예측 레이팅에 맞게 오름차순 정렬후 1번부터 인덱스를 정해주면 된다. 다만 싫어요부터 1부터 정해줘야 한다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
int a[200001],ans[200001];
vector<pair<int, int>> v1, v2, v3, v4;
string s;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		cin >> s;
		v1.clear(); v2.clear();
		for (int i = 0; i < n; i++) {
			if (s[i] == '0')v1.push_back({ a[i],i });
			else v2.push_back({ a[i],i });
		}
		sort(v1.begin(), v1.end());
		sort(v2.begin(), v2.end());
		int start = 1;
		for (int i = 0; i < v1.size(); i++) {
			ans[v1[i].second] = start++;
		}
		for (int i = 0; i < v2.size(); i++) {
			ans[v2[i].second] = start++;
		}
		for (int i = 0; i < n; i++)cout << ans[i] << ' ';
		cout << '\n';
	}
 
}

C. Set or Decrease

Problem - C - Codeforces

Problem - C - Codeforces

 

문제

 

n개의 수가 담긴 배열과 k가 주어진다. 2가지중에 원하는 동작을 골라 여러번 할 수 있을때 배열에 담긴 모든 원소의 합이 k 이하로 되게하는 최소 동작의 수를 출력하는 문제

동작 1 : a[i] = a[i]-1

동작 2 : i, j를 골라 a[i]= a[j]

 

풀이

 

배열을 오름차순으로 정렬하고 각 인덱스까지 가장 작은원소로 바꿧을때의 값들중에서 최소를 출력한다. 

각 인덱스까지 가장 작은 원소로 바꿧을때 값을 구하는 과정은 소스를 참고

 

코드

 

#include <bits/stdc++.h>
using namespace std;
long long a[200001];
long long sum[200001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		long long n, k;
		cin >> n >> k;
		long long allsum = 0;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			allsum += a[i];
		}
		if (allsum <= k) {
			cout << 0 << '\n';
			continue;
		}
		if (n == 1) {
			if (a[0] <= k)cout << 0 << '\n';
			else cout << a[0] - k << '\n';
			continue;
		}
	
		sort(a, a + n);
		sum[n - 1] = a[n - 1] - a[0];
		long long ans = allsum - k;
		for (int i = n - 2; i > 0; i--) {
			sum[i] = sum[i + 1] + a[i] - a[0];
		}
		for (int i = 1; i < n; i++) {
			long long t = allsum - sum[i];
			long long cnt = n - i;
			if (t <= k) {
				ans = min(ans,cnt);
			}
			else {
				long long dif = t - k;
				cnt++;
				long long div = dif / cnt;
				if (dif % cnt)div++;
				cnt--;
				ans = min(ans, div + cnt);
			}
		}
		cout << ans << '\n';
	}
 
}

 

 

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.