Educational Codeforces Round 123 (Rated for Div. 2)

A. Doors and Keys

 r, g, b, R, G, B의 6자리 문자열이 주어졌을 때 R앞에 r, G앞에 g, B앞에 b가 등장하는 지 확인해서 모두 등장하면 YES, 아아니면 NO를 출력한다.

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int tc;
string str;
 
int main() {
	cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
	cin >> tc;
	while (tc--) {
		cin >> str;
		bool chk1 = 0;
		bool chk2 = 0;
		bool chk3 = 0;
		bool possible1 = 0;
		bool possible2 = 0;
		bool possible3 = 0;
		for (int i = 0; i < 6; i++) {
			if (str[i] == 'r') chk1 = 1;
			if (str[i] == 'g') chk2 = 1;
			if (str[i] == 'b') chk3 = 1;
			if (str[i] == 'R' && chk1) possible1 = 1;
			if (str[i] == 'G' && chk2) possible2 = 1;
			if (str[i] == 'B' && chk3) possible3 = 1;
		}
		if (possible1 && possible2 && possible3) {
			cout << "YES" << '\n';
		}
		else cout << "NO\n";
	}
}

 

B. Anti-Fibonacci Permutation

 n이 주어졌을 때, 1~n으로 구성된 순열에서 연속된 수열이 피보나치 수열이 되지 않게 n개의 순열을 구성하면 된다.  (pi−2+pi−1≠pi)

 피보나치 수열이 되지 않으려면 n 부터 1로 진행하는 수열이면 앞의 두 수 합이 뒤에 올 수 보다 커지기 때문에 큰 수부터 작은 수로 진행해 나가면 되겠다고 생각했다. 

 4를 예로 들면 4 3 2 1, 4 2 3 1, 4 1 3 2 이렇게 n-1 방식과 3 4 2 1의 한 가지를 출력해 총 n 가지 순열을 만들었다. 

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int tc, n;
 
int main() {
	cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
	cin >> tc;
	while (tc--) {
		cin >> n;
		for (int j = n - 1; j >= 1; j--) {
			cout << n << ' ';
			cout << j << ' ';
			for (int k = n - 1; k >= 1; k--) {
				if (k == j) continue;
				cout << k << ' ';
			}
			cout << '\n';
		}
		cout << n-1 << ' ' << n << ' ';
		for (int i = n - 2; i >= 1; i--) {
			cout << i << ' ';
		}
		cout << '\n';
	}
}

 

C. Increase Subarray Sums

 n개의 연속된 수열이 있다. f(k)는 특정 수열 k 부분에 x 만큼 더했을 때, 부분 연속 수열의 최댓값을 의미한다. 맨 처음에 생각한 아이디어는 누적합을 이용하여 구간합을 구하고 거기에 min(구간 차이, k) * x 를 곱해주는 방식으로 했다. 그런데 TLE가 떠서 전처리를 따로 해주었다. chk[i] 배열을 만들어 chk : 수열에서 i 개의 연속된 수열의 최댓값으로 설정했다. 그러면 일일이 i개의 연속된 수열을 구하지 않고 바로 찾아 쓰면 되기 때문에 n^2이 된다?  f(0) ~ f(n) 까지 출력할 때는 브루트포스를 이용하여 일일이 최대 ans 값을 갱신해주었다. 자세한 과정은 아래 과정 참고!

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int tc;
int n, x;
int arr[5001];
ll sum[5001];
ll chk[5001];
 
int main() {
	cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
	cin >> tc;
	while (tc--) {
		cin >> n >> x;
		memset(arr, 0, sizeof(arr));
		memset(sum, 0, sizeof(sum));
		for (int i = 0; i <= n; i++) {
			chk[i] = -98765432100;
		}
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
			sum[i] = sum[i - 1] + arr[i];
		}
		ll ans = 0;
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k < j; k++) {
				ll tmp = sum[j] - sum[k];
				chk[j - k] = max(chk[j - k], tmp);
			}
		}
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				ll tmp;
				if (j <= i) {
					tmp = chk[j] + j * x;
				}
				else tmp = chk[j] + i * x;
				ans = max(ans, tmp);
			}
			cout << ans << ' ';
		}
		cout << '\n';
	}
}