codeforces round 819 (div.1 + div.2) A-C

A. Mainak and Array

 

 

문제 :

길이가 $n$인 수열 $a$가 있다. 수열 $a$의 부분을 선택해서 순서를 유지한 채로 위치를 바꿀 수 있다. 즉 $1\leq l\leq r\leq n$인 $l,r$에 대하여 $a_l = a_{l+1}, a_{l+1}=a_{l+2}, ..., a_{r-1}=a_r, a_r=a_l$의 연산을 원하는 만큼 반복할 수 있다. 이때 $a_n - a_1$의 최댓값을 알아보면 된다.

 

 

풀이 :

$1 < l\leq r < n$인 경우 연산을 아무리 적용해도 결과는  바뀌지 않으므로 $a_n-a_1$이 답의 후보가 된다.

$1 = l\leq r < n$인 경우 $a_1, a_2,..., a_{n-1}$중 최솟값을 $a_1$로 옮긴 후 $a_n$에서 뺀 값이 답의 후보가 된다.

$1 < l\leq r = n$인 경우 $a_2, a_3,...,a_n$중 최댓값을 $a_n$으로 옮긴 후 $a_1$을 뺀 값이 답의 후보가 된다.

$l=1, r=n$인 경우 인접한 두 원소 중 앞에서 뒤를 뺀 값($a_i-a_{i+1}, i+1>n$이면 $i+1=1$)이 답의 후보가 된다. 첫 번째 경우가 이 경우에 포함된다.

위의 경우에서 가장 큰 값이 답이 된다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
 
void solve() {
	int n;
	cin >> n;
	vector<int> ar(n);
	int M = 0, m = 1e3;
	for (int& x : ar) {
		cin >> x;
		if (x > M) M = x;
		if (x < m) m = x;
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (ar[i] - ar[(i + 1) % n] > ans) ans = ar[i] - ar[(i + 1) % n];
	}
	if (ans < M - ar.front()) ans = M - ar.front();
	if (ans < ar.back() - m) ans = ar.back() - m;
	cout << ans << '\n';
	return;
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

B. Mainak and Interesting Sequence

 

 

문제 :

$n, m$이 주어졌을 때 특정 조건을 만족하는 길이가 $n$인 수열 $a$를 찾으면 된다.

조건 1) $a_1+a_2+\ldots +a_n=m$이다.

조건 2) 수열 $a$에서 $a_i$보다 작은 모든 값들의 XOR값이 $0$이 되어야 한다. 즉 $a_i$보다 작은 모든 값들의 XOR값을 $p_i$라 할 때 $p_1 = p_2 =\ldots = p_n = 0$이어야 한다.

$1\leq a_i$이고 답이 여러 개 존재하면 아무것이나 하나만 출력하면 된다.

 

 

풀이 :

(1) $1\leq a_i$이므로 수열의 모든 값이 1일 때의 합 $n$보다 $m$이 작으면, 즉 $n>m$이면 수열을 만들 수 없다.

(2) $n$이 짝수일 때 $m$이 홀수이면 수열을 만들 수 없다. (짝수개의 숫자들의 합은 짝수가 돼야 하니까)

이 두 가지 경우를 제외하면 항상 수열을 만들 수 있다.

 

어떤 정수에 자기 자신을 XOR 한 값은 0 임을 이용하면 된다. ($x$^$x$=0) 가능한 경우는

(1) $n$이 짝수일 때 수열의 모든 값이 같거나

(2) $n$이 짝수일 때 수열의 $n-2$개의 값이 같고 이 값들과 다른 $2$개의 값이 같거나

(3) $n$이 홀수일 때 수열의 $n-1$개의 값이 같고 이 값들보다 큰 다른 $1$개의 값이 있으면 된다.

 

 

코드 :

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

void solve() {
	int n, m;
	cin >> n >> m;
	if (n > m || n % 2 == 0 && m % 2) {
		cout << "no\n";
		return;
	}
	cout << "yes\n";
	if (m % n == 0) for (int i = 0; i < n; i++) cout << m / n << ' ';
	else {
		int t = m / n;
		if (n % 2) {
			for (int i = 1; i < n; i++) cout << t << ' ';
			cout << m - t * (n - 1);
		}
		else {
			for (int i = 2; i < n; i++) cout << t << ' ';
			t = m - t * (n - 2);
			cout << t / 2 << ' ' << t / 2;
		}
	}
	cout << '\n';
	return;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

 

---

 

C. Jatayu's Balanced Bracket Sequence

 

 

문제 :

길이가 $2n$인 문자열 $s$가 있다. 문자열은 '(', ')'문자 두 가지로 구성되어있고 첫 번째 위치는 1부터 시작한다. $1\leq l < r\leq 2n$인 $l, r$이 있을 때, 문자열에서 $l$부터 $r$까지 괄호의 짝이 맞으면 $l$과 $r$은 연결되어있다고 한다. 이를 그래프로 표현했을 때 몇 개의 연결된 그래프가 있는지 알아보면 된다.

 

예를 들어 "()(())"의 문자열은 $(l,r)$이 (1, 2), (1, 6), (3, 6), (4,5) 일 때 완전하다고 할 수 있고 이를 그래프로 표현하면

이런 그림이 된다. 이때 연결된 그래프는 (2-1-6-3), (4-5) 이렇게 2개가 된다.

 

 

풀이 :

'('가 연속으로 2번 나오면 새로운 그래프가 만들어진다. (첫 번째 괄호가 두 번째의 괄호로 만들어지는 그래프와 어떻게 해도 연결될 수가 없기 때문에) 이 부분은 전체에도 적용될 수 있으므로 '('가 연속 2번 나오면 그래프가 하나 더 만들어지는 성질을 이용해서 전체 문자열에서 '('가 연속으로 2번 나오는 횟수를 세주고 그 수에 1을 더한 값이 답이 된다.(1을 더하는 것은 1의 위치에서 만들어지는 그래프를 더해줘야 하기 때문에)

 

 

코드 :

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

void solve() {
	int n, cnt = 0;
	string str;
	cin >> n >> str;

	int ans = 1;
	for (int i = 0; i < 2 * n - 1; i++) {
		if (str[i] == '(' && str[i + 1] == '(') ans++;
	}
	cout << ans << '\n';
	return;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---