Educational Codeforces Round #101(Div.2) A~D

버추얼을 돌았는데, 점점 머리가 안 좋아지는 것 같은 묘한 느낌을 받는다. 실력이란 게 쉽게 늘어나는 것은 아니라지만 늘어나기는 커녕 줄어드는 것 같은 느낌은 착각이라고 믿고 싶다. 버추얼을 까고 나서 업솔빙하면서 라운드에 대한 평가를 보니까 쉬운 라운드였다고 해서 자괴감이 들었다. 단 A번에서 헤맨 사람이 나뿐은 아니라는 사실이 좀 위안이 되었다.

A. Regular Bracket Sequence

괄호들과 '?' 로 이루어진 문자열이 주어진다. '?'들을 괄호로 바꿔서 짝이 맞는 괄호 문자열을 만들 수 있느냐에 관한 문제이다. 이때 짝이 맞는 괄호라고 하면 반사적으로 스택을 떠올리는 것이 알고리즘을 하는 자의 본능이다. 하지만 A번에 그딴 게 나올 리가 없다. 문제를 잘 읽어 보면, '(' 과 ')' 은 각각 하나씩만 들어가 있다는 조건이 있다. 따라서 여는 괄호, 닫는 괄호에 대해 각각 짝을 맞출 수 있는 '?'가 존재하면 된다. 이는 다음과 같이 코드로 옮길 수 있다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
typedef long long ll;
using namespace std;
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	int tc;
	cin >> tc;
	for (int z = 0; z < tc; z++) {
		int possible = 1;
		string s;
		cin >> s;
		int len = s.length();
		if (s.length() % 2 == 1) { possible = 0; } //문자열 길이 홀수면 절대불가
		else {
			int c = 0;
			for (int i = 0; i < len; i++) {
				if (s[i] == ')') { c--; }
				else { c++; }
				if (c < 0) { possible = 0; }
			}
			c = 0; //c를 초기화 해주는 걸 잊지 말자
			for (int i = len-1; i >= 0; i--) {
				if (s[i] == '(') { c--; }
				else { c++; }
				if (c < 0) { possible = 0; }
			}
		}
		cout << (possible ? "YES\n" : "NO\n");
 
	}
 
	return 0;
 
}

B. Red and Blue

A보다 쉽다고 느꼈다. 주어진 두 배열 r,b의 prefix sum들 중 가장 큰 것을 골라서 더해주면 된다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
typedef long long ll;
using namespace std;
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	int tc;
	cin >> tc;
	for (int z = 0; z < tc; z++) {
		int n, arr[105], asum = 0;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
		}
		for (int i = 1; i < n; i++) {
			arr[i] += arr[i - 1];
		}
		for (int i = 0; i < n; i++) {
			asum = max(asum, arr[i]);
		}
 
 
		int m, brr[105], bsum = 0;
		cin >> m;
		for (int i = 0; i < m; i++) {
			cin >> brr[i];
		}
		for (int i = 1; i < m; i++) {
			brr[i] += brr[i - 1];
		}
		for (int i = 0; i < m; i++) {
			bsum = max(bsum, brr[i]);
		}
 
		cout << max(asum + bsum, 0) << "\n";
 
	}
 
	return 0;
 
}

C. Building a Fence

높이가 K인 울타리들을 n개 연속해서 배치해야 한다. 그런데 울타리를 배치할 땅이 평평하지가 않다. 울타리를 설치할 칸의 높이가 연속해서 주어지고, 거기에 조건에 맞게 울타리를 배치할 수 있는지를 판단하는 문제이다. 조건은 다음과 같다.

• 그 전 칸의 울타리와 최소 한 칸은 겹쳐야 한다.
• 처음 울타리/마지막 울타리는 땅에 붙어 있어야 한다.
• 울타리의 아래가 땅에 비해 k-1이상의 높이에 위치하면 안 된다.

그러면 처음 울타리가 땅에 붙어 있어야 함은 자명하다. 그 다음 울타리부터는 그 전 칸의 울타리의 위치에 따라 울타리를 설치할 수 있는 높이의 범위가 정해진다. 그 범위가 모든 울타리에 대해 존재하고, 또 마지막 울타리를 땅에 붙여서 설치할 수 있으면 문제의 조건을 만족시킨다. 그대로 구현하면 된다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
typedef long long ll;
using namespace std;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int tc;
	cin >> tc;
	for (int z = 0; z < tc; z++) {
		int n, k, h[200005];
		pair<int, int> bottom[200005]; //울타리의 아래쪽이 위치할 수 있는 범위를 나타낸다
		cin >> n >> k;
		for (int i = 0; i < n; i++) {
			cin >> h[i];
		}
		bottom[0] = { h[0],h[0] }; //처음에는 무조건 땅에 붙어 있어야
		for (int i = 1; i < n; i++) {
			bottom[i] = { max(h[i],bottom[i - 1].first - (k - 1)),min((h[i] + k - 1), bottom[i - 1].second + k - 1) };
		}

		int possible = 1;
		if (!(bottom[n - 1].first <= h[n - 1] && h[n - 1] <= bottom[n - 1].second)) {
			possible = 0;
		}
		for (int i = 0; i < n; i++) {
			if (bottom[i].first > bottom[i].second) { possible = 0; }
		}

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

	}

	return 0;

}

D. Ceil Divisions

1,2,3,...,n인 수열 a가 있다. 이때 서로 다른 x,y를 골라서 $$ a_x $$ 와 $$ a_y $$ 에 대해, $$ a_x=ceil(a_x/a_y) $$ 로 만들어 줄 수 있다. 이 연산을 최대 n+5번 해서, 주어진 수열을 n-1개의 1과 1개의 2로 이루어진 수열로 바꾸면 된다. 언제나 가능하다는 게 증명되어 있다고 한다.

그럼 1,2는 그대로 놔두고, 3부터 연산을 적용시켜 주면 3~n-1 부분은 쉽게 1로 만들 수 있다. 그럼 마지막 남은 n은 어떻게 하는가? 하나의 2가 남아 있으므로 2로 계속 나눠 가면서 1로 만들어 가는 방법을 생각해 볼 수 있다. 하지만 n의 최댓값이 20만이므로 1로 죽이려면 최대 약 18번의 연산이 소모될 것이고 그러면 연산 횟수의 총합이 n+5번을 넘게 될 것이다. 따라서 2의 적당한 제곱수를 이용하는 방법을 생각해 볼 수 있다. 나는 32를 사용했다. 수열 중간에 32를 일부러 남겨 놓은 다음 남은 n을 32로 나눠가면서 1을 만드는 것이다. 그리고 남은 32는 2를 이용해서 5번만에 처리한다. 64나 128을 사용하면 연산 횟수를 한두 번 더 줄일 수 있지만 제한만 만족하면 되므로 아무래도 좋다. 그리고 n이 32보다 작은 경우에는 그냥 2를 사용해서 n을 1로 만들어 줘도 n+5번 제한에 충분히 들어간다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
typedef long long ll;
using namespace std;
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	int tc;
	cin >> tc;
	for (int z = 0; z < tc; z++) {
		int n;
		cin >> n;
		int ans = 0;
		if (n >= 32) {
			for (int i = 3; i < n; i++) {
				if (i != 32) {
					ans++;
				}
			}
 
			int tmp = n;
			while (tmp > 1 && tmp != 32) {
				if (tmp % 32 == 0) { tmp = tmp / 32; }
				else { tmp = tmp / 32 + 1; }
				ans++;
			}
 
			ans += 5;
 
			cout << ans << "\n";
			for (int i = 3; i < n; i++) { //3부터 n-1까지 1로 만들어준다
				if (i != 32) {
					cout << i << " " << n << "\n";
				}
			}
			tmp = n;
			while (tmp > 1 && tmp != 32) { //32를 이용해 n을 1로 만들어줌
				if (tmp % 32 == 0) { tmp = tmp / 32; }
				else { tmp = tmp / 32 + 1; }
				cout << n << " " << 32 << "\n";
			}
			for (int i = 0; i < 5; i++) { //남은 2 하나를 이용해 32도 1로
				cout << 32 << " " << 2 << "\n";
			}
 
 
		}
		else if (n == 3) {
			cout << "2\n3 2\n3 2\n";
		}
		else { //n이 32보다 작다
			for (int i = 3; i < n; i++) {
				if (i != 32) {
					ans++;
				}
			}
			int tmp = n;
			while (tmp > 1) {
				if (tmp % 2 == 0) { tmp = tmp / 2; }
				else { tmp = tmp / 2 + 1; }
				ans++;
			}
 
			cout << ans << "\n";
			for (int i = 3; i < n; i++) {
				if (i != 32) {
					cout << i << " " << n << "\n";
				}
			}
			tmp = n;
			while (tmp > 1) {
				if (tmp % 2 == 0) { tmp = tmp / 2; }
				else { tmp = tmp / 2 + 1; }
				cout << n << " " << 2 << "\n";
			}
		}
 
 
 
	}
 
	return 0;
 
}