Codeforces Round #690 (Div. 3) 풀이

 

 

A. Favorite Sequence

 

입력으로 문제의 그림과 같이 위치가 바뀐 수열이 들어온다. 

다시 원래의 수열을 출력해주면 된다. 

(처음엔 바뀐 수열을 출력하라는 줄 알았다. 꽤나 비슷한 실수를 한 사람들이 많은 것 같다)

 

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

int A[301];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		for (int i = 1; i <= n; i++) cin >> A[i];
		for (int i = 1; i <= n / 2; i++) cout << A[i] << ' ' << A[n - i + 1] << ' ';
		if (n % 2) cout << A[(n + 1) / 2];
		cout << '\n';
	}
}

 

 

B. Last Year's Substring

 

하나 이하의 구간을 제거해서 "2020"을 만들 수 있는지에 대한 문제이다. 
n이 최대 200이므로 4개를 남기고 자르는 모든 경우를 비교해보면 된다.

 

#include<bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		string s; cin >> s;
		bool chk = false;
		int cnt = 0;
		for (int i = 0; i < 5; i++) {
			int j = sz(s) - (4 - i) - 1;
			string tmp = "";
			for (int k = 0; k < sz(s); k++) {
				if (k >= i && k <= j) continue;
				tmp += s[k];
			}
			if (tmp == "2020") chk = true;

		}
		if (chk) cout << "YES\n";
		else cout << "NO\n";
	}
}

 

 

C. Unique Number

 

각 자릿수의 합이 고정된 상태에서 가장 작은 수를 구해야 하므로, 

일의 자리부터 채울 수 있는 가장 큰 값으로 채워나간다. 
채우지 못하는 경우에는 -1을 출력한다.

 

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int x; cin >> x;
		vector<int> ans;
		for (int i = 9; i >= 1; i--) {
			if (i <= x) {
				ans.push_back(i);
				x -= i;
			}
			else continue;
		}
		if (x != 0) cout << -1 << '\n';
		else {
			reverse(all(ans));
			for (int i : ans)cout << i;
			cout << '\n';
		}
	}
}

 

 

D. Add to Neighbour and Remove

 

배열의 누적합을 pre[i]라고 하면, 원소가 모두 같게 만들었을 때

해당 원소의 값은 반드시 pre[1], pre[2] , ..., pre[n]중의 하나가 되어야 한다. 

문제에서 주어진 연산을 어떻게, 몇번을 적용하던지 항상 배열의 제일 처음 원소는 pre[i] 값 중 하나로 나오기 때문이다.

따라서 pre[1] ~ pre[n]의 값 중 하나로 배열의 모든 원소를 바꿀 수 있는지를 체크하고, 그중 가장 적은 연산 수를 구한다.

 

#include<bits/stdc++.h>
using namespace std;
int A[3001];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		for (int i = 1; i <= n; i++) cin >> A[i];
		int pre = 0;
		int ans = (int)1e9;
		for (int k = 1; k <= n; k++) {
			pre += A[k];
			int cnt = k - 1;
			int tmp = 0;
			bool chk = true;
			for (int i = k + 1; i <= n; i++) {
				if (A[i] == pre) {
					if (tmp != 0) chk = false;
				}
				else if (tmp + A[i] <= pre) {
					if (tmp == 0) tmp += A[i];
					else {
						tmp += A[i];
						cnt++;
					}
					if (tmp == pre) tmp = 0;
				}
				else {
					chk = false;
					break;
				}
			}
			if (tmp != 0) chk = false;
			if (chk) ans = min(ans, cnt);
		}
		cout << ans << '\n';
	}
}

 

E1/E2. Close Tuples (easy/hard version)

 

easy version은 hard version에서 k와 m값이 고정된 경우이다. (답이 mod로 나눠주지 않는 long long 범위인걸 주의) 

따라서 hard version을 통해서 이해해보자. 

 

원소 m개를 뽑았을 때, 최솟값과 최댓값의 차이가 k이하가 되는 tuple의 개수를 구하는 문제이다.

우선 배열을 오름차순으로 정렬해두고, i = 1 ~ n-m+1 에 대해서 A [i]가 최솟값인 경우를 생각한다. 

A[i]가 최솟값이기 때문에 나머지 m-1개의 원소는 i+1 ~ n의 범위에서 뽑아져야 한다.

이때, 뽑히는 원소는 A[i] + k 이하여야 하므로, A[i] + k 이하인 원소의 index 중 최댓값을 lower_bound로 구한 뒤, 

가능한 원소들 중 m-1개를 뽑는 경우의 수를 더한다. 

 

[E1 code]

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int A[200001];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		vector<int> cnt(2 * n + 1);
		for (int i = 1; i <= n; i++) {
			cin >> A[i];
			cnt[A[i]]++;
		}
		sort(A + 1, A + 1 + n);
		ll ans = 0;
		for (int i = 1; i <= n - 2; i++) {
			ll k1 = lower_bound(A + 1, A + 1 + n, A[i] + 2) - A;
			k1 += cnt[A[i] + 2] - 1;
			if (k1 - i + 1 >= 2) ans += (k1 - i)*(k1 - i - 1) / 2;
		}
		cout << ans << '\n';
	}
}

 

[E2 code]

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = (int)1e9 + 7;
const double PI = acos(-1);
int A[200001];
#define MAX_C 200000
ll fac[MAX_C + 1], facinv[MAX_C + 1];
ll mpow(ll a, ll x) { //a^x
	ll res = 1;
	while (x > 0) {
		if (x % 2) res *= a;
		res %= MOD;
		a = (a*a) % MOD;
		x /= 2;
	}
	return res;
}

ll combi(ll n, ll r) {
	return (((fac[n] * facinv[r]) % MOD)*facinv[n - r]) % MOD;
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	fac[0] = 1;
	for (int i = 1; i <= MAX_C; i++) fac[i] = (fac[i - 1] * i) % MOD;
	facinv[MAX_C] = mpow(fac[MAX_C], MOD - 2);
	for (int i = MAX_C - 1; i >= 0; i--) facinv[i] = facinv[i + 1] * (i + 1) % MOD;

	while (T--) {
		int n, m, k; cin >> n >> m >> k;
		vector<int> cnt(2*n+1);
		for (int i = 1; i <= n; i++) {
			cin >> A[i];
			cnt[A[i]]++;
		}
		sort(A + 1, A + 1 + n);
		ll ans = 0;
		for (int i = 1; i <= n-m+1; i++) {
			int k1 = lower_bound(A + 1, A + 1 + n, A[i] + k) - A;
			k1 += cnt[A[i] + k] - 1;
			if (k1 - i + 1 >= m) ans += combi(k1 - i, m-1);
			ans %= MOD;
		}
		cout << ans << '\n';
	}
}

 

F. The Treasure of the Segments

 

왼쪽 좌표와 오른쪽 좌표를 따로 보관한 후, 이분탐색을 이용하는 풀이가 훨씬 간단하지만, 문제를 보고 세그 트리가 생각이 나서 좌표 압축 + 세그 트리로 해결하였다.

 

먼저 좌표압축을 한 뒤에, 주어진 구간들을 오름차순으로 정렬한다.

구간 (a, b)가 구간 (l, r)에 겹치게 되는 경우는 l ≤ b ≤ r 이거나, l ≤ a ≤ r 인 경우이다.

구간이 담겨있는 배열을 A라고 하면, A[i]와 겹치는 구간의 수를 구할 때에는

 

1. A[1] ~ A[i-1]의 구간의 끝이 A[i]에 포함되는 경우

2. A[i+1] ~ A[n]의 구간의 시작이 A[i]에 포함되는 경우

를 각각 고려해주면 된다. 

 

따라서 먼저 구간들의 시작 부분을 세그트리에 모두 넣어준다.

그리고, 현재 구간을 확인하고 나서는 현재 구간의 시작은 세그 트리에서 제거해주고, 구간의 끝은 추가해준다.

 

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MAX = (int)2e9;
int tr[1600001];
void init(int x, int s, int e) {
	if (s == e) tr[x] = 0;
	else {
		init(x * 2, s, (s + e) / 2);
		init(x * 2 + 1, (s + e) / 2 + 1, e);
	}
}
void update(int x, int s, int e, int i, int val) {
	if (i > e || i < s) return;
	tr[x] += val;
	if (s != e) {
		update(x * 2, s, (s + e) / 2, i, val);
		update(x * 2 + 1, (s + e) / 2 + 1, e, i, val);
	}
}
int sum(int x, int s, int e, int l, int r) {
	if (s > r || e < l) return 0;
	if (s >= l && e <= r) return tr[x];
	else return sum(x * 2, s, (s + e) / 2, l, r) + sum(x * 2 + 1, (s + e) / 2 + 1, e, l, r);
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	//	freopen("input.txt", "r", stdin);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		vector<pii> v(n + 1);
		vector<int> val;
		map<int, int> mp;
		for (int i = 1; i <= n; i++) {
			cin >> v[i].first >> v[i].second;
			val.push_back(v[i].first);
			val.push_back(v[i].second);
		}
		sort(all(val));
		val.erase(unique(all(val)), val.end());
		for (int i = 0; i < sz(val); i++) {
			mp[val[i]] = i + 1;
		}
		for (int i = 1; i <= n; i++) {
			v[i].first = mp[v[i].first];
			v[i].second = mp[v[i].second];
		}
		sort(v.begin() + 1, v.end());
		int ans = MAX;
		int N = sz(val);
		fill(tr, tr + 4 * N + 1, 0);
		for (int i = 1; i <= n; i++) {
			update(1, 1, N, v[i].first, 1);
		}
		for (int i = 1; i <= n; i++) {
			ans = min(ans, n - sum(1, 1, N, v[i].first, v[i].second));
			update(1, 1, N, v[i].first, -1);
			update(1, 1, N, v[i].second, 1);
		}
		cout << ans << '\n';
	}
}