코드포스(Codeforces) Round #662 풀이

이번 Div 2는 생각보다 조금 쉬운 편에 속했던 것 같다.
그리고 민트를 찍었다.

A (https://codeforces.com/contest/1393/problem/A)
각 테스트케이스마다 N이 주어진다.
NxN의 체스판에 2명이 서로 돌아가면서 체스판을 채울 때 필요한 턴의 수를 구하는 것이다.
직접 채워보면 규칙이 보인다.
N / 2 + 1을 출력하면 된다.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
 
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		cout << (n + 2) / 2 << "\n";
	}
}

B (https://codeforces.com/contest/1393/problem/B)
맵에 다 넣고 완전 탐색을 돌리면 TLE가 나서 map<갯수, 판자의 set, greater<>>으로 잡은 뒤, 위에서부터 봐주면서 여러 조건들만 봐주면 된다.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> cnt(100001);
map<int, set<int>, greater<>> mp;
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
 
	int n;
	cin >> n;
	while (n--) {
		int a;
		cin >> a;
		cnt[a]++;
	}
 
	for (int i = 1; i <= 100000; i++)
		if (cnt[i]) mp[cnt[i]].insert(i);
 
	int k;
	cin >> k;
	while (k--) {
		char c;
		cin >> c;
		int a;
		cin >> a;
 
		mp[cnt[a]].erase(a);
		if (c == '+') cnt[a]++;
		else --cnt[a];
		mp[cnt[a]].insert(a);
 
		int one = 0, two = 0;
		for (const auto &b : mp) {
			if (b.second.empty()) continue;
			if ((one && two >= 2) || b.first < 2) break;
 
			if (one) {
				if (b.first >= 4) two = 2;
				else two = (two + 1ULL) * b.second.size();
				continue;
			}
 
			if (b.first >= 8) one = two = 2;
			else if (b.first >= 6) one = ++two;
			else if (b.first >= 4) {
				one = 1;
				if (b.second.size() >= 2) two = 2;
			}
			else ++two;
 
			one *= b.second.size();
			two *= b.second.size();
		}
 
		if (one && two >= 2) cout << "YES";
		else cout << "NO";
 
		cout << "\n";
	}
}

C (https://codeforces.com/contest/1393/problem/C)
B번에서 대략 1시간을 끌어서 C를 못 풀 줄 알았는데 생각보다 금방 풀었다. Div2 A와 B는 30분 내로 안정적으로 솔브하고 싶다..
같은 종류의 파이를 최대한 멀리 배정해야한다.
우선 각 파이의 갯수로 정렬을 한 뒤에, 제일 많은 갯수의 파이들만 뽑아서 먼저 배열을 하자.
1: 2, 4: 2, 6: 2, 7: 1
2개가 가장 많기 때문에, 1, 4, 6을 뽑고 배열을 하면,
146_146과 같이 된다.
이제 남은 숫자들로 언더바(_)를 골고루 채워넣으면 된다.
146 7 146와 같이 배열할 수 있고
한번 더 해보자.
1: 2, 4: 3, 6: 2, 7: 1
3개가 가장 많은 파이이기 때문에
4_4_4와 같이 배열하고, 남은 1, 6, 7을 활용하여 언더바에 적절히 채워넣으면 된다.
4 16 4 167 4와 같이 배열할 수 있고, 이 경우 답은 2가 된다.

언더바의 갯수는 파이의 최대 갯수 - 1개이고, 남은 숫자를 언더바의 갯수로 나눠주면 최적의 해를 구할 수 있다.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
 
	int T; cin >> T;
	while (T--) {
		int n, mx = 0; cin >> n;
		vector<pair<int, int>> v(100001);
		for (int i = 0; i < n; i++) {
			int a; cin >> a;
			v[a] = {v[a].first + 1, a};
			mx = max(mx, v[a].first);
		}
 
		sort(v.begin(), v.end(), greater<>());
 
		int ans = 0;
		for (const auto &i : v)
			if (i.first == mx) {
				ans++;
				n -= i.first;
			}
 
		ans += n / (mx - 1) - 1;
		cout << ans << "\n";
	}
}

실수를 줄이고 신중해져야 할 것 같다.
감점이 너무 많았다.