Codeforces Round #788 (Div. 2) 1681 → 1679

https://codeforces.com/contest/1670

https://codeforces.com/contest/1670

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

 

A. Prof. Slim

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

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

문제

 

n길이의 배열 a가 주어진다. 두개의 값 부호가 다른 인덱스 i,j를 골라 a[i]와 a[i]의 부호를 바꿔주는 연산을 원하는만큼 할 수 있을때 a를 non-decreasing order로 sort할 수 있는지 판별하는 문제

 

풀이

 

기본적으로 음수는 가장 앞 인덱스에 몰아주고 sorting되있는지 확인하면 된다.

 

코드

 

    #include <bits/stdc++.h> 
    using namespace std;
    long long a[100001];
    long long b[100001];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            int n;
            cin >> n;
            int cnt = 0;
            for (int i = 1; i <= n; i++) {
                cin >> a[i];
                if (a[i] < 0)cnt++;
                b[i] = abs(a[i]);
            }
            for (int i = 1; i <= cnt; i++) {
                b[i] = -b[i];
               
            }
            
            bool flag = true;
            for (int i = 2; i <= n; i++) {
                if (b[i - 1] > b[i]) {
                    flag = false;
                    break;
                }
            }
            if (flag)cout << "YES\n";
            else cout << "NO\n";
            
            
        }
     
    }

 

B. Dorms War

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

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

 

문제

 

n길이의 string s가 주어지고 k개의 특별한 문자가 주어진다. 각 초당 특별한 문자 앞을 지우는 프로그램이 실행 될 때 ( 특별한 문자 앞에 아무것도 없으면 프로그램은 중단된다) 몆초동안 프로그램이 실행되는지 계산하는 문제

 

풀이

 

특별한 문자들끼리의 최대 거리를 출력해주면 된다. 다만 제일 앞에 있는 문자는 0과의 거리로 계산한다.

 

 

코드

 

    #include <bits/stdc++.h> 
    using namespace std;
    string s;
    int d[100010];
    bool check[130];
    vector<int> v;
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            for (int i = 'a'; i <= 'z'; i++)check[i] = false;
            v.clear();
            int n;
            string s;
            cin >> n >> s;
            int num;
            cin >> num;
            while (num--) {
                char c;
                cin >> c;
                check[c] = true;
            }
            for (int i = 0; i < n; i++) {
                if (check[s[i]]) {
                    v.push_back(i);
                }
            }
            if (v.size() == 0) {
                cout << 0 << '\n';
            }
            else {
                int MAX = v[0];
                for (int i = 1; i < v.size(); i++) {
                    MAX = max(MAX, v[i] - v[i - 1]);
                }
                cout << MAX << '\n';
            }
        }
     
    }

C. Palindrome Basis

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

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

문제

 

 n길이의 permutation a,b가 주어지고 따로 c 가 주어진다. a나 b의 인덱스중 원하는 원소를 골라 c를 구성했을 때 c도 permutation인 경우의 수를 출력하는 문제

 

 

풀이

 

각 a와 b가 각 인덱스에 있는 수들끼리 그룹을 묶어주고, 어떤 수를 쓰는지 확정이 아닌 그룹갯수만큼 2를 곱해주면 된다.

 

코드

    #include <bits/stdc++.h> 
    using namespace std;
    const long long mod = 1000000007;
    int a[100001];
    int b[100001];
    int c[100001];
    int p[100001];
    bool check[100001];
    bool visited[100001];
    int Find(int x) {
        if (x == p[x])return x;
        else return p[x] = Find(p[x]);
    }
    void Union(int x, int y) {
        x = Find(x); y = Find(y);
        if (check[x] || check[y]) {
            check[x] = check[y] = true;
        }
        p[y] = x;
    }
    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++) {
                p[i] = i;
                check[i] = visited[i] = false;
            }
            for (int i = 1; i <= n; i++)cin >> a[i];
            for (int i = 1; i <= n; i++)cin >> b[i];
            long long ans = 1;
            for (int i = 1; i <= n; i++) {
                cin >> c[i];
                Union(a[i], b[i]);
                if (a[i] == b[i])c[i] = a[i];
                if (c[i]) {
                    check[Find(a[i])] = true;
                }
            }
            for (int i = 1; i <= n; i++) {
                int i2 = Find(i);
                if (visited[i2] == false) {
                    visited[i2] = true;
                    if (check[i2] == false) {
                        ans *= 2LL;
                        ans %= mod;
                        check[i2] = true;
                    }
                }
            }
            cout << ans << '\n';
     
        }
     
    }

 

 

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

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