Educational Codeforces Round 119 (Rated for Div. 2) 1522 -> 1562

Dashboard - Educational Codeforces Round 119 (Rated for Div. 2) - Codeforces

Dashboard - Educational Codeforces Round 119 (Rated for Div. 2) - Codeforces

!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!

 

 

A. Forbidden Subsequence

Problem - A - Codeforces

Problem - A - Codeforces

문제

 

circle로 된 n개의 원소를 가진 수열이 있다. 여기서 s가 주어지는데 s[i] =='E'라면 a[i] == a[i+1]이고, 'N' 이라면 a[i] != a[i+1] 이다. 이때 이 조건에 맞는 수열이 있으면 YES 아니면 NO를 출력하는 문제

 

풀이

 

N이 1개만 있고 E가 나머지로 가득 채울때만 NO이고 나머지 모든 경우는 된다

 

 

코드

 

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		string s;
		cin >> s;
		int cnt = 0;
		for (int i = 0; i < s.size(); i++) {
			if (s[i] == 'E')cnt++;
		}
		if (cnt == s.size() - 1) {
			cout << "NO\n";
		}
		else cout << "YES\n";
	}
}

 

 

B.   Triangles on a Rectangle

Problem - B - Codeforces

Problem - B - Codeforces

 

문제

 

왼쪽 밑이 0,0  오른쪽 위가 w,h인 사각형에 각 변에서 점들이 주어진다. 각 점은 최소 2개이상이며, 한변에서 같은 2개의 점과 다른변에서 1개를 골라서 만들 수 있는 삼각형의 최대 넓이 *2를 출력하는 문제

 

풀이

 

x축과 평행한 변의 최대 삼각형 넓이는 x축에서 가장 긴 길이 * h 이고, y축과 평행한 변의 최대 삼각형 넓이는 y축에서 가장 긴 길이 * x이므로 각 변 마다 max값을 갱신하여 출력해주면 된다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
long long a[200001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		long long w, h,ans=0;
		cin >> w >> h;
		for (int i = 0; i < 4; i++) {
			int k;
			cin >> k;
			for (int j = 0; j < k; j++) {
				cin >> a[j];
			}
			long long dif = a[k - 1] - a[0];
			if (i < 2) {
				ans = max(ans, dif * h);
			}
			else {
				ans = max(ans, dif * w);
			}
		}
		cout << ans << '\n';
	}
}

C. BA-String

Problem - C - Codeforces

Problem - C - Codeforces

 

문제

 

n,k,x와 n길이의 string s 가 주어진다. s는 'a'와 '*'로만 이루어져 있고 *는 0개 부터 k개까지 b로 바꿀 수 있다. 바꿀 수 있는 모든 문자열 중에서 x번째로 작은 수를 출력하는 문제

 

풀이

 

한번에 연결된 * 를 덩어리라고 했을때 각 덩어리안에 * 개수마다 k개의 경우의 수를 만들 수 있고, 다음 덩어리에서는 그동안 합쳐진 경우의수의 배수만큼 또 만들 수 있다. 이렇게 개수를 증가시키다가 x의 차례가오면 정리한 경우의 수에 맞게 b갯수를 출력시킨다. 

 

코드

 

#include <bits/stdc++.h>
using namespace std;
long long d[2001];
string s;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		long long n, k, x;
		cin >> n >> k >> x;
		for (int i = 0; i < n; i++)d[i] = x+1LL;
		cin >> s;
		if (x == 1) {
			for (int i = 0; i < n; i++) {
				if (s[i] == 'a')cout << s[i];
			}
			cout << '\n';
			continue;
		}
		long long start = 1, sum = 1;
		for (int i = s.size() - 1; i >= 0; i--) {
			if (s[i] == '*') {
				bool flag = false;
				int istart = i;
				for (int j = i - 1; j >= 0; j--) {
					if (s[j] == '*') {
						istart = j;
					}
					else break;
				}
				for (int j = istart; j <= i; j++) {
					d[j] = sum;
					for (int o = 1; o <= k; o++) {
						if (start + sum > x) {
							flag = true;
							break;
						}
						else start += sum;
						if (start == x) {
							flag = true;
							break;
						}
					}
					if (flag)break;
				}
				sum = start;
				if (flag)break;
				i = istart;
			}
		}
		x--;
		for (int i = 0; i < s.size(); i++) {
			if (s[i] == '*') {
				for (int j = 0; j < k; j++) {
					if (x - d[i] >= 0) {
						x -= d[i];
						cout << 'b';
					}
					else break;
				}
			}
			else cout << s[i];
		}
		cout << '\n';
	}
 
}

 

 

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.