티스토리 뷰

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

 

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

 

codeforces.com

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

 

A. Balanced Substring

Problem - A - Codeforces

 

Problem - A - Codeforces

 

codeforces.com

문제

 

입력으로 'a' 와 'b'로만 이루어진 문자열이 주어질 때, a 갯수와 b 갯수가 똑같은 l~r 범위를 출력하는 문제

 

풀이

 

각 문자열 인덱스마다 , 양 옆에 다른게 하나라도 있으면 해당 범위 출력

 

코드

 

#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--) {
		int n; string s;
		cin >> n >> s;
		int l=-1,r=-1;
		for (int i = 0; i < n; i++) {
			if (i > 0) {
				if (s[i] != s[i - 1]) {
					l = i - 1; r = i;
					break;
				}
			}
			if (i < n - 1) {
				if (s[i] != s[i + 1]) {
					l = i; r = i + 1;
					break;
				}
			}
		}
		if (l == -1)cout << l << ' ' << r << '\n';
		else cout << l + 1 << ' ' << r + 1 << '\n';
		
	}
}

 

 

B. Chess Tournament

Problem - B - Codeforces

 

Problem - B - Codeforces

 

codeforces.com

문제

 

n명이 체스 토너먼트를 한다. 여기서 각 선수들은 나머지 모든 선수들과 경기를 하는데 

1. 아무한테도 안지거나

2. 최소 한 경기는 이기거나

상태를 만족해야한다. i 선수가 j선수에게 이겼을때는 i행 j열에서 +, 졌을때는 -, 무승부 일때는 = 를출력하는 문제

 

풀이

 

2번 상태의 선수들을 따로 모아서 i 번째 2번상태 선수가 (i+1)번째 선수를 이기도록 한다.

단 1번 상태의 선수는 무조건 =를 출력 하며 , 2번 상태의 선수가 1~2명일 경우에는 어떻게 해서든 조건을 만족 시킬 수 없으므로 NO를 출력한다

 

 

코드

 

#include <bits/stdc++.h>
using namespace std;
char ans[101][101];
int next1[51];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int n;
		string s;
		cin >> n >> s;
		int cnt2 = 0;
		vector<int> v;
		for (int i = 0; i < n; i++) {
			if (s[i] == '2') {
				cnt2++;
				v.push_back(i);
			}
		}
		if (cnt2 > 0 && cnt2 < 3) {
			cout << "NO\n";
			continue;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				ans[i][j] = '#';
			}
		}
		for (int i = 0; i < n; i++)next1[i] = 0;
		cout << "YES\n";
		for (int i = 0; i < cnt2; i++) {
			next1[v[i]] = v[(i + 1) % cnt2];
			ans[v[i]][next1[v[i]]] = '+';
			ans[next1[v[i]]][v[i]] = '-';
		}
		for (int i = 0; i < n; i++) {	
			for (int j = 0; j < n; j++) {
				if (i == j) {
					ans[i][j] = 'X';
					continue;
				}
				if (s[i] == '1' || s[j] == '1') {
					ans[i][j] = '=';
					continue;
				}
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (ans[i][j] == '#')ans[i][j] = '+';
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (ans[i][j] != '#')continue;
				if (ans[j][i] == '+')ans[i][j] = '-';
				else if (ans[j][i] == '-')ans[i][j] = '+';
				else ans[j][i] = '=';
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cout << ans[i][j];
			}
			cout << '\n';
		}
	}
}

C. Jury Meeting

Problem - C - Codeforces

 

Problem - C - Codeforces

 

codeforces.com

문제

 

주어진 배열을 임의로 배치했을 때, 왼쪽부터 돌아가면서 1씩 제거하면서 자기의 순번을 말한다. 이때 연속으로 자기 순번을 2번이상 말하게 되면 그 배치는 not nice 이고 이외의 배치는 nice가 된다. 가능한 nice 경우의 수를 출력하는 문제

 

풀이

 

우선 정렬을 했을때 , 가장 큰 원소와 2번째로 큰 원소가 2이상 차이나면 어떻게든 nice한 배열을 만들 수 없다.

이후 전체 답 ( n! ) 에서 안되는 값을 빼주면 되는데, 가장 큰 원소 뒤에 두번째로 큰 값이 하나도 없는 경우이다.

가장 큰원소와 2번째 큰원소를 전체에서 뺀 값을 cnt라고 했을 때, (가장 큰 원소 뒤에 cnt를 배치하는 경우의 수 * 가장 큰 원소 앞에 나머지 원소들을 배치해주는 경우의 수) 를 전체 답에서 빼주면 된다.  

 

 

코드

 

#include <bits/stdc++.h>
using namespace std;
long long a[200001],d[200001],pac[200010];
const long long mod = 998244353;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int n,dif = 0;
		long long ans = 0;
		cin >> n;
		for (int i = 0; i < n; i++)cin >> a[i];
		sort(a, a + n);
		if (a[n - 1] - a[n-2] > 1) {
			cout << 0 << '\n';
			continue;
		}
		ans = 1;
		for (long long i = n; i > 1; i--) {
			ans *= i;
			ans %= mod;
		}
		if (a[n - 1] == a[n - 2]) {
			cout << ans << '\n';
		}
		else {
			long long cnt = 0,start=1;
			for (int i = 0; i < n; i++) {
				if (a[n - 1] - 1 != a[i]) {
					cnt++;
				}
			}
			cnt--;
			if (cnt == 0) {
				for (int i = n - 1; i > 1; i--) {
					start *= i;
					start %= mod;
				}
				ans -= start;
				while (ans < 0)ans += mod;
				cout << ans << '\n';
				continue;
			}
			pac[0] = 1;
			for (long long i = 1; i <= cnt; i++) {
				pac[i] = pac[i - 1] * (cnt - (i - 1LL));
				pac[i] %= mod;
			}
			long long dif = n - 1 - cnt;
			for (long long i = 1; i <= dif; i++) {
				start *= i;
				start %= mod;
			}
			long long sum = 0;
			for (long long i = cnt; i >= 0; i--) {
				sum += pac[i] * start;
				dif++;
				start *= dif;
				start %= mod;
				sum %= mod;
			}
			ans -= sum;
			while (ans < 0)ans += mod;
			cout << ans << '\n';
		}
	}
}

레이팅 변화:

1425 -> 1466 (+41)

 

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

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