[CodeForces] #905 (Div.3) A~F 업솔빙

안녕하세요 Gliver 입니다.

이번 글은 코드포스 #905 (Div.3) 에 대해 업솔빙하는 글입니다.

 

 

 

 

A. Morning

단순 구현 문제로, 버튼을 누르는 횟수와 이동하는 횟수를 구해서 출력하면 된다.

 

 

	#include <bits/stdc++.h>
	using namespace std;
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int tc; cin >> tc;
	while (tc--) {
	string s; cin >> s;
	s = "1" + s;
	int ans = 0;
	for (int i=0; i<=3; i++) {
	int a, b;
	a = (s[i] == '0' ? 10 : s[i]-'0');
	b = (s[i+1] == '0' ? 10 : s[i+1]-'0');
	ans += abs(b - a);
	}
	cout << ans + 4 << '\n';
	}
	return 0;
	}

view raw A.cpp hosted with ❤ by GitHub

 

 

 

B. Chemistry

개인적으로 조금 복잡하게 생각한 문제이다.

 

팰린드롬을 만들 수 있는 경우는 다음 두 가지 상황으로 제한할 수 있다.

• 모든 문자의 개수가 짝수개인 경우
• 하나의 문자의 개수가 홀수개이고, 나머지 모든 문자의 개수가 짝수개인 경우

 

따라서, 문자열을 적절히 제거하여 홀수개인 문자가 1개 이하가 되도록 만들 수 있으면 된다.

이는, 홀수개인 문자의 개수에서 $k$를 뺀 값이 1 이하 이면 된다는 의미이다.

 

 

	#include <bits/stdc++.h>
	using namespace std;
	void solve() {
	int n, k; cin >> n >> k;
	string s; cin >> s;
	vector<int> cnt(26, 0);
	for (auto u : s) {
	cnt[u-'a'] += 1;
	}
	int odd = 0;
	for (int i=0; i<26; i++) {
	if (cnt[i] % 2) odd += 1;
	}
	if (odd - k <= 1) cout << "YES" << '\n';
	else cout << "NO" << '\n';
	}
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int tc; cin >> tc;
	while (tc--) solve();
	return 0;
	}

view raw B.cpp hosted with ❤ by GitHub

 

 

 

C. Raspberries

모든 원소의 곱이 $k$로 나누어 떨어지도록 하는 연산의 최소 횟수를 구하는 문제이다.

$k$ 는 2, 3, 4, 5 중에 하나이므로, 문제를 쉽게 해결할 수 있다.

 

$k$가 소수(prime number)인 경우(2, 3, 5)에는 해당 수의 배수를 무조건 만들어야 한다.

$k$가 4인 경우는 2의 배수 2개를 만들거나 4의 배수를 만들면 된다.

 

 

	#include <bits/stdc++.h>
	using namespace std;
	void solve() {
	int n, k; cin >> n >> k;
	vector<int> arr(n);
	for (auto &u : arr) cin >> u;
	if (k == 4) {
	int best1, best2;
	best1 = best2 = 100;
	for (auto u : arr) { // 'k - (나머지)' 만큼 필요
	if (u % k == 0) best1 = 0;
	else best1 = min(best1, (k - (u % k)));
	}
	int even = 0;
	for (auto u : arr) {
	if (u % 2 == 0) even += 1;
	}
	if (even >= 2) best2 = 0;
	else if (even == 1) best2 = 1;
	else best2 = 2;
	cout << min(best1, best2) << '\n';
	}
	else {
	int best = 100;
	for (auto u : arr) { // 'k - (나머지)' 만큼 필요
	if (u % k == 0) best = 0;
	else best = min(best, (k - (u % k)));
	}
	cout << best << '\n';
	}
	}
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int tc; cin >> tc;
	while (tc--) solve();
	return 0;
	}

view raw C.cpp hosted with ❤ by GitHub

 

 

 

D. In Love

현재 상황에서 겹치지 않는 쌍이 존재하는지를 묻는 문제이다.

 

시작점의 좌표가 끝점의 좌표보다 큰 경우가 존재한다면, 해당 두 쌍은 겹치지 않는다.

따라서, 시작점의 최대값 > 끝점의 최소값 인 경우에는 적어도 하나의 겹치지 않는 쌍이 존재한다.

 

 

	#include <bits/stdc++.h>
	using namespace std;
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int q; cin >> q;
	multiset<int> s, e;
	while (q--) {
	char op;
	int a, b;
	cin >> op >> a >> b;
	if (op == '+') {
	s.insert(a);
	e.insert(b);
	}
	if (op == '-') {
	s.erase(s.find(a));
	e.erase(e.find(b));
	}
	if (s.size() && *e.begin() < *s.rbegin()) cout << "YES" << '\n';
	else cout << "NO" << '\n';
	}
	return 0;
	}

view raw D.cpp hosted with ❤ by GitHub

 

 

 

E. Look Back

이 문제는 다음과 같은 사실을 만족한다.

• arr[i] > arr[i+1] 인 쌍이 존재한다면 arr[i+1]에 연산을 1회 이상 시행해야 한다.
• 인덱스 i를 기준으로 i 이전의 원소들이 non-decreasing 상태를 만족하면, [1, i] 구간은 연산을 시행할 필요가 없다.

 

위의 사실을 이용하면, 첫 원소부터 시작하여 arr[i] <= arr[i+1] 이 되게끔 arr[i+1]에 최소 연산을 시행해 주면 문제를 해결할 수 있다.

원소에 2를 곱하는 형식으로 구현하면 매우 큰 수가 나오므로 배열의 원소에 2를 곱하는 방식이 아닌 다른 방식의 처리가 필요하다.

 

원소에 2를 곱하는 형식이 아닌 원소에 연산을 한 횟수를 저장하는 형식으로 문제를 해결할 수 있다.

어떤 원소 $a$에 연산을 $p$번 하게 되면 $a \cdot 2^{p}$의 형태로 나타낼 수 있다.

따라서, $a, b, p$가 정해진 상태에서 $a \cdot 2^{p} \leq b \cdot 2^{q}$를 만족하는 $q$의 최소값을 구할 수 있다.

 

 

	#include <bits/stdc++.h>
	using namespace std;
	using ll = long long;
	void solve() {
	ll n; cin >> n;
	vector<ll> arr(n);
	for (auto &u : arr) cin >> u;
	ll ans = 0;
	ll cnt = 0;
	for (int i=1; i<n; i++) {
	if (arr[i] < arr[i-1]) {
	ll bef = arr[i-1];
	ll cur = arr[i];
	while (cur < bef) {
	cur *= 2;
	cnt += 1;
	}
	}
	if (arr[i] > arr[i-1]) {
	ll bef = arr[i-1];
	ll cur = arr[i];
	while (cur >= 2*bef) {
	bef *= 2;
	cnt -= 1;
	}
	}
	cnt = max(cnt, 0LL);
	ans += cnt;
	}
	cout << ans << '\n';
	}
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int tc; cin >> tc;
	while (tc--) solve();
	return 0;
	}

view raw E.cpp hosted with ❤ by GitHub

 

 

 

F. You Are So Beautiful

이 문제는 이해하는 데 시간이 좀 걸렸다.

 

다음의 조건을 만족하는 $[l, r]$ 쌍의 개수를 구하면 되는 문제이다.

• $b = [a_l, \ a_{l+1} \, \ \cdots \ , \ a_{r-1}, \ a_r]$은 기존의 배열 $a$에서 유일한 subsequence(부분 문자열)이어야 한다.
  (여기서 subsequence는 연속일 필요는 없다)

예를 들어, a = [2, 3, 2, 3] 인 경우를 살펴보자.

l=0, r=1 인 경우
b = [2, 3] 이며, [a[0], a[1]]을 제외한 [a[0], a[3]]인 경우도 [2, 3]이 되므로 l=0, r=1인 경우는 조건을 만족하지 않는다.

l=0, r=2인 경우
b = [2, 3, 2] 이며, [a[0], a[1], a[2]]를 제외한 어떠한 subsequence도 [2, 3, 2]가 되지 못하므로 조건을 만족한다.

 

$b = [a_l, \ a_{l+1} \, \ \cdots \ , \ a_{r-1}, \ a_r]$ 가 조건을 만족하는 경우는 아래의 조건을 만족하는 경우다.

• 인덱스 $l$ 이전에 $a_l$과 같은 값이 존재하지 않는다.
• 인덱스 $r$ 이후에 $a_r$과 같은 값이 존재하지 않는다.

따라서, $a_l$은 처음으로 등장한 값이어야 하며, $a_r$은 마지막으로 등장한 값이어야 한다.

등장하는 모든 값에 대해 첫 인덱스와 마지막 인덱스를 매칭시키면 빠르게 모든 쌍을 구할 수 있다.
(누적 합 배열을 만들어 처리하면 $O(n)$에 모든 쌍을 구할 수 있다)

 

 

	#include <bits/stdc++.h>
	using namespace std;
	void solve() {
	int n; cin >> n;
	vector<int> arr(n);
	for (auto &u : arr) cin >> u;
	set<int> st;
	vector<bool> lt(n, false), rt(n, false);
	for (int i=0; i<n; i++) {
	if (!st.count(arr[i])) lt[i] = true;
	st.insert(arr[i]);
	}
	st.clear();
	for (int i=n-1; i>=0; i--) {
	if (!st.count(arr[i])) rt[i] = true;
	st.insert(arr[i]);
	}
	vector<int> psum(n, 0);
	psum[n-1] = rt[n-1];
	for (int i=n-2; i>=0; i--) {
	psum[i] = psum[i+1] + rt[i];
	}
	long long ans = 0;
	for (int i=0; i<n; i++) {
	if (lt[i]) ans += psum[i];
	}
	cout << ans << '\n';
	}
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int tc; cin >> tc;
	while (tc--) solve();
	return 0;
	}

view raw F.cpp hosted with ❤ by GitHub