Codeforces Round #661 (Div.3)

A. Remove Smallest

https://codeforces.com/contest/1399/problem/A

 

인자가 n개인 배열을 정렬했을 때 계단수인지 확인한다.

정렬된 인자 사이의 차가 1보다 크면 계단수가 아니다.

 

시간 복잡도는 O(NlogN)이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>
using namespace std;
int t, N;
int arr[51];
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> t;
	while (t--) {
		cin >> N;
		bool flag = 1;
		for (int i = 0; i < N; i++)cin >> arr[i];
		sort(arr, arr + N);
		for (int i = 0; i < N - 1; i++) {
			if (abs(arr[i] - arr[i + 1]) <= 1)continue;
			else {
				cout << "NO\n";
				flag = 0;
				break;
			}
		}
		if(flag==1)cout << "YES\n";
	}
}

 

B. Gifts Fixing

https://codeforces.com/contest/1399/problem/B

 

크기가 N인 배열이 2개 주어진다(각각 사탕, 오렌지의 개수).

우리는 3개의 연산을 이용해 각각의 배열의 값을 같게 만들어야 한다.

쓸 수 있는 연산은 다음과 같다.

1. 사탕을 1개 먹는다.

2. 오렌지를 1개 먹는다.

3. 사탕과 오렌지를 1개씩 먹는다.

 

그러므로, 우리는 먼저 사탕과 오렌지 배열의 최솟값을 찾고, 최솟값까지 몇 개를 먹어야 되는지 알아야 한다.

 

예를 들어, 사탕의 개수가 { 1, 2, 3 }이고, 오렌지의 개수가 { 5, 2, 4 }라면,

사탕의 개수를 { 1, 1, 1 }, 오렌지의 개수를 { 2, 2, 2 } 로 맞추는 것이 정답이다.

 

각각의 index에 대해 연산의 최솟값은 max(사탕만 먹는 연산의 횟수, 오렌지만 먹는 연산의 횟수)이다.

 

시간 복잡도는 O(N)이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>
using namespace std;
int t, N;
int app[51], ora[51];
long long mn = 2100000000, mn2 = 2100000000;
long long cnt;
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> t;
	while (t--) {
		cin >> N; mn = 2100000000;
		mn2 = 2100000000; cnt = 0;
		for (int i = 0; i < N; i++) {
			cin >> app[i];
			mn = min(mn, (long long)app[i]);
		}
		for (int i = 0; i < N; i++) {
			cin >> ora[i];
			mn2 = min(mn2, (long long)ora[i]);
		}
		for (int i = 0; i < N; i++) {
			cnt += max(app[i] - mn, ora[i] - mn2);
		}
		cout << cnt << "\n";
	}
}

 

C. Boats Competition

https://codeforces.com/contest/1399/problem/C

 

크기가 N인 배열을 입력받고, 임의의 정수 s에 대해 두 원소를 합했을 때 s를 만들 수 있는 최댓값 k를 최대화하는 문제이다.

 

예를 들어,

{ 6, 6, 6, 6, 6, 6, 8, 8 }에 대해

s가 될 수 있는 수는 12, 14, 16이다.

 

s = 12일 때, { 6, 6 }, { 6, 6 }, { 6, 6 } 으로 s를 만들 수 있어 k = 3이다.

s = 14일 때, { 6, 8 }, { 6, 8 } 인 경우가 가능해 k = 2이다.

s = 16일 때는 { 8, 8 } 만 가능해 k = 1이다.

답은 k의 값들 중 최댓값인 3이다.

 

여기서, 우리는 s가 주어질 때의 k 값을 모두 구해놓으면 k의 최댓값이 답이 될 수 있다는 것을 알 수 있다.

 

문제의 조건에 따라 원소에 들어갈 수 있는 수는 원소의 크기 N(<=50)보다 작거나 같다.

따라서, 2 <= s <= 100이다.

s가 2~100일 때 가질 수 있는 순서쌍의 개수를 map에 저장한다.

map[s] = k의 형식으로 저장한다.

 

그 뒤, map을 순회하며 저장된 k 중의 최댓값을 구한다.

실제 소스 코드에서는 k가 최대가 되는 s값에 대해 k를 다시 구해줬다.

 

시간 복잡도는 O(N^2)이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <map>
using namespace std;
int t, N;
int w[51];
int mx, mxnum, ans;
bool used[51];
map<int, int> m;//sum, cnt
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> t;
	while (t--) {
		cin >> N;
		for (int i = 1; i <= N; i++) {
			cin >> w[i];
			used[i] = 0;
		}
		m.clear();
		for (int s = 2; s <= 100; s++) {
			for (int i = 1; i < s; i++) {
				if (count(w+1, w + N+1, i)) {
					m[s] += min(count(w + 1, w + N + 1, i), count(w + 1, w + N + 1, s - i));
				}
			}
		}
		/*
		for (int i = 1; i <= N; i++) {
			for (int j = i; j <= N; j++) {
				if (i == j)continue;
				m[w[i] + w[j]]++;
			}
		}
		*/
		mx = 0; mxnum = 0; ans = 0;
		for (auto i : m) {
			if (mx < i.second) {
				mxnum = i.first;
			}
			mx = max(mx, i.second);
		}
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (used[i] || used[j])continue;
				if (i == j)continue;
				if (w[i] + w[j] == mxnum) {
					used[i] = used[j] = 1;
					ans++;
				}
			}
		}
		cout << ans << "\n";
	}
}

 

D. Binary String To Subsequences

https://codeforces.com/contest/1399/problem/D

 

문제 이해가 어려웠는데, 문제를 조금 풀어서 설명하면,

 

1. 길이가 N인 0과 1로 이루어진 문자열 s이 주어진다.

2. 이 문자열의 subsequence는 이 문자열의 임의의 인덱스를 삭제시킨 문자열로 정의한다.

임의의 인덱스를 몇개든 없앨 수 있지만, 순서는 바꿀 수 없다. (ex: 1011101에서 11100으로 바꿀 수 없다.)

3. 우리는 s의 각 자리수 a에 대해서 모든 a가 s의 subsequence에 포함되도록 하고 싶다.

4. 이 때, subsequence는 반드시 "101010..." 또는 "010101..."의 형태여야 한다.

5. subsequence의 개수가 가장 적을 때, 각 a가 몇 번째 subsequence인지 출력한다.

 

구현에 앞서, 예제를 살펴보자.

 

s = 10101의 경우, 모든 a가 s의 subsequence = 10101에 포함될 수 있기 때문에

1 1 1 1 1을 출력한다.

 

s = 01010000의 경우, 처음 5개의 a는 subsequence = 01010에 포함될 수 있기 때문에 1의 값을 갖고,

뒤의 3개의 a는 각각 고유한 subsequence = 0에 포함되어야 하므로

1 1 1 1 1 2 3 4를 출력한다.

 

 

구현 방법은 다음과 같다.

 

1. 일단 모든 subsequence의 가장 마지막 자리(마지막 자리가 a가 몇 번째 subsequence에 포함되는지를 결정하기 때문이다)를 저장한다(소스 코드에선 vector<char> last).

 

2. a가 저장된 last[i]^1과 같다면, 기존의 subsequence에 포함될 수 있으므로, 기존의 last[i]에 ^= 1을 해준다.

 

3. 만약 모든 last[i]^1과 다르다면, 기존의 subsequence에 포함될 수 없으므로, 새로운 subsequence를 만들고, subsequence의 마지막 자리를 a로 설정한다.

 

4. 만약 a가 모든 last[i]와 다르고, a의 다음 자리 b 또한 a와 같다면, b도 모든 last[i]와 다름이 자명하다. 그러므로 모든 last[i]와 같은지 체크하는 절차 없이 바로 subsequence를 하나 추가해준다.

 

이것을 naive하게 구현하면 시간복잡도가 O(N^2)인데, 처음에 TLE가 나길래 4번을 추가해서 AC를 받을 수 있었다.

 

2, 3번 과정에서 lower_bound를 이용하면 총 시간복잡도를 O(NlogN)으로 줄일 수 있다.

 

문제 푸는 동안에 binary search를 쓸 생각을 하지 못했다. 앞으로 더 열심히 해야겠다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <map>
#include <cstring>
using namespace std;
int t, N;
string str;
vector<char> last;
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> t;
	while (t--) {
		cin >> N;
		cin >> str;
		last.clear();
		bool good = 0, lastgood = 0;
		string ans = "";
		for (int i = 0; i < N; i++) {
			if (i != 0 && good == 0 && str[i] == str[i - 1]) goto lol;
			good = 0;
			for (int j = 0; j < last.size(); j++) {
				if ((str[i] - '0') ^ 1 == last[j] - '0') {
					last[j] ^= 1;
					good = 1;
					ans += to_string(j + 1);
					ans += ' ';
					break;
				}
			}
			if (good == 1) continue;
			lol:
			last.push_back(str[i]);
			ans += to_string(last.size());
			ans += ' ';
		}
		cout << last.size() << '\n';
		cout << ans << '\n';
	}
}