티스토리 뷰
Educational Codeforces Round 113 (Rated for Div. 2) , 1425 -> 1466 (+41)
Edyy 2021. 9. 10. 16:02Dashboard - 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
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
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
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)
자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !
틀린 부분은 감사히 지적받겠습니다.
'Algorithm > 코드포스' 카테고리의 다른 글
Codeforces Round #746 (Div. 2) , 1603 -> 1550 (-53) (0) | 2021.10.04 |
---|---|
Codeforces Round #744 (Div. 3) , 1466 -> 1561 (+95) (0) | 2021.09.29 |
Codeforces Round #743 (Div. 2) , Unrated (0) | 2021.09.19 |
Codeforces Round #742 (Div. 2) , 1484 -> 1424 (-60) (0) | 2021.09.06 |
Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2) , 1397 -> 1482 (+85) (0) | 2021.08.30 |