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;
}