Codeforces Global Round 20 1577 → 1632

https://codeforces.com/contest/1672

Dashboard - Codeforces Global Round 20 - Codeforces

 

!!!! 모든 답은 제 풀이일 뿐 공부를 위한 올바른 정해가 아닐 수 있습니다 !!!!

 

A. Log Chopping

https://codeforces.com/contest/1672/problem/A

Problem - A - Codeforces

문제

 

길이가 n인 배열 a가 주어진다 각 a[i]들의 수를 x라고했을때 x = y+z (y,z는 정수)형태로 쪼갤 수 있고 errorgorn 과 maomao90가 서로 돌아가면서 쪼갠다. 자유롭게 쪼개다가 본인 턴에 쪼갤 수 없으면 진다. errorgorn이 먼저 시작하고 둘다 최선으로 두었을때 이기는 사람을 출력하는 문제

 

풀이

 

각 수마다 어떤 형태를 쪼개든 똑같은 횟수만큼 쪼갤 수 있다. 쪼개는 회수를 세준 후 계산하여 출력해주면 된다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
long long a[51];
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)cin >> a[i];
        long long sum = 0;
        for (int i = 0; i < n; i++)sum += (a[i] - 1);
        if (sum % 2)cout << "errorgorn\n";
        else cout << "maomao90\n";
    }
}

 

B. I love AAAB

https://codeforces.com/contest/1672/problem/B

Problem - B - Codeforces

 

문제

 

string s1과 s2가 있다. s1은 최초로 빈 문자열이고 s2는 입력으로 주어진다. 아래의 operation을 원하는 만큼 했을 때 B를 만들 수 있으면 YES 아니라면 NO를 출력하는 문제

AB 형태(A는 원하는갯수만큼 늘릴 수 있다) 를 골라 s1의 원하는 위치에 추가하는 연산 

 

풀이

 

각 B마다 앞에있는 A의 개수가 B이상인지 체크하고 마지막 문자열이 B라면 답은 YES 아니라면 NO

 

코드

 

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

C. Unequal Array

https://codeforces.com/contest/1672/problem/C

Problem - C - Codeforces

문제

 

n길이의 배열 a가 주어지고 배열의 equailty 를 1<=i <=n-1 , a[i]=a[i+1]의 개수로 정의한다. 이때 아래의 operation을 통해서 equality를 1이하로 만드는 최소의 연산수를 출력하는 문제

 

 

풀이

 

가장 왼쪽의 a[i]=a[i+1]인 i와 가장 오른쪽의 a[i]=a[i+1]을 골라 그 사이를 operation으로 바꿔주는 값을 계산해주면 된다.

 

코드

#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--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)cin >> a[i];
        int l = 300000, r = -1;
        for (int i = 1; i < n; i++) {
            if (a[i] == a[i + 1]) {
                l = min(l, i);
                r = i;
            }
        }
        //cout << l << ' ' << r << '\n';
        if (r == -1 || l==r) {
            cout << 0 << '\n';
            continue;
        }
        if (l + 1 == r) {
            cout << 1 << '\n';
            continue;
        }
        l++; r--;
        cout << r - l + 1 << '\n';
    }
}

 

F1. Array Shuffling

https://codeforces.com/contest/1672/problem/F1

Problem - F1 - Codeforces

문제

 

n길이의 배열 a와 b가있다. b는 a배열을 원하는데로 섞은 배열이다. 인덱스 i , j를 골라 b[i]와 b[j]를 스왑하는 연산을 통하여 a배열로 만들어야 하는데 최대로 스왑하게 만든 배열을 출력하는 문제

 

풀이

 

각 수마다 벡터에 인덱스를 담아 , 각 벡터마다 같은 인덱스들을 cyclic 해주면 된다. 핵심 원리는 다른 수들끼리 자리를 회전시켜주는 것

 

코드

#include <bits/stdc++.h>
using namespace std;
int a[200001];
vector<int> v[200001],num;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        num.clear();
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            v[i].clear();
        }
        int MAX = 1;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            if (v[a[i]].empty())num.push_back(a[i]);
            v[a[i]].push_back(i);
            MAX = max(MAX, (int)v[a[i]].size());
        }
        for (int i = 0; i < MAX; i++) {
            vector<int> temp,temp2;
            for (int j = 0; j < num.size(); j++) {
                if (v[num[j]].size() >= (i + 1)) {
                    temp.push_back(v[num[j]][i]);
                    temp2.push_back(num[j]);
                }
            }
            //cout << "확인\n";
            //for (int j = 0; j < temp.size(); j++) {
            //    cout << temp[j] << ' ';
            //}
            //cout << '\n';
            //for (int j = 0; j < temp.size(); j++) {
            //    cout << temp2[j] << ' ';
            //}
            //cout << '\n';
            for (int j = 0; j < temp.size(); j++) {
                a[temp[j]] = temp2[(j+1)%temp.size()];
              /*  cout << temp[j] << ' ' << temp2[(j + 1) % temp.size()] << '\n';*/
            }
        }
        for (int i = 1; i <= n; i++)cout << a[i] << ' ';
        cout << '\n';
        
    }
}

 

 

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

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