Codeforces Round #794 (Div. 2) 1537 → 1589

https://codeforces.com/contest/1686

Dashboard - Codeforces Round #794 (Div. 2) - Codeforces

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

 

A. Everything Everywhere All But One

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

Problem - A - Codeforces

문제

 

n길이의 배열 a가 주어진다. 한번의 operation에 n-1개의 원소를 골라 평균으로 바꿔주는 연산을 유한하게 했을때 모든 원소를 같게 만들 수 있으면 YES 아니라면 NO를 출력하는 문제

 

풀이

 

모든 원소를 탐색하면서 i번째에 있는 원소를 제외한 평균이 a[i] 인게 있다면 답은 YES 아니라면 NO를 출력하는 문제

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    int 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;
            int sum = 0;
            for (int i = 0; i < n; i++) {
                cin >> a[i];
                sum += a[i];
            }
            int n2 = n - 1;
            bool flag = false;
            for (int i = 0; i < n; i++) {
                int sum2 = sum - a[i];
                if (sum2 % n2 == 0) {
                    if ((sum2 / n2) == a[i]) {
                        flag = true;
                        break;
                    }
                }
            }
            if (flag)cout << "YES\n";
            else cout << "NO\n";
     
        }
     
    }

 

B. Odd Subarrays

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

Problem - B - Codeforces

문제

 

n길이의 permutation이 주어진다. 주어진 permutation을 적절하게 잘라 inversion의 개수가 홀수인 subarray의 개수를 최대로 구하는 문제

 

풀이

 

inversion의 개수가 1이되는 순간 바로 자르는 방식으로 구한다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    int a[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 MAX = 0;
            int ans = 0;
            for (int i = 0; i < n; i++) {
                cin >> a[i];
                if (MAX > a[i]) {
                    ans++;
                    MAX = 0;
                    continue;
                }
                MAX = max(MAX, a[i]);
            }
            cout << ans << '\n';
     
        }
     
    }

C. Circular Local MiniMax

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

Problem - C - Codeforces

문제

 

n길이의 배열 a가 주어진다. 주어진 a를 임의로 원형으로 재배치해서 a[i-1] < a[i]  > a[i+1] 모든 i에 대하여 a[i-1] > a[i] < a[i+1] 로 만들 수 있다면 YES와 그러한 배열을 출력하고 아니라면 NO를 출력하는 문제

 

풀이

 

a를 정렬하여 가장 작은수 -> 가장 큰수 대로 배치해본 후 확인 , 가장 큰수 -> 가장 작은 수를 배치하여 확인

가장 큰수 - n/2의 인덱스를 차례대로 배치하여 확인, 가장 작은수 + n/2 인덱스를 차례대로 배치하여 확인한 후 하나라도 답이 된다면 그러한 배열을 출력하고 아니라면 NO를 출력하면 된다.

 

코드

    #include <bits/stdc++.h>
    using namespace std;
    int a[100001];
    int 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;
            for (int i = 0; i < n; i++)cin >> a[i];
            sort(a, a + n);
            int l = 0, r = n - 1;
            int cnt = 0;
            while (true) {
                if (cnt % 2) {
                    b[cnt] = a[l++];
                }
                else {
                    b[cnt] = a[r--];
                }
                cnt++;
                if (cnt >= n)break;
            }
            bool flag = true;
            for (int i = 0; i < n; i++) {
                int il = i - 1, ir = i + 1;
                if (il < 0)il = n - 1;
                if (ir >= n)ir = 0;
                if (b[i] > b[il] && b[i] > b[ir])continue;
                if (b[i] < b[il] && b[i] < b[ir])continue;
                flag = false;
                break;
            }
            if (flag) {
                cout << "YES\n";
                for (int i = 0; i < n; i++)cout << b[i] << ' ';
                cout << '\n';
                continue;
            }
            flag = true;
            l = 0; r = n - 1;
            cnt = 0;
            while (true) {
                if (cnt % 2) {
                    b[cnt] = a[l++];
                }
                else {
                    b[cnt] = a[r--];
                }
                cnt++;
                if (cnt >= n)break;
            }
            for (int i = 0; i < n; i++) {
                int il = i - 1, ir = i + 1;
                if (il < 0)il = n - 1;
                if (ir >= n)ir = 0;
                if (b[i] > b[il] && b[i] > b[ir])continue;
                if (b[i] < b[il] && b[i] < b[ir])continue;
                flag = false;
                break;
            }
            if (flag) {
                cout << "YES\n";
                for (int i = 0; i < n; i++)cout << b[i] << ' ';
                cout << '\n';
                continue;
            }
            flag = true;
            cnt = 0;
            int n2 = n / 2;
            if (n % 2)n2++;
            for (int i = n - 1; i >= 0; i--) {
                b[cnt++] = a[i];
                if (i - n2 < 0)break;
                b[cnt++] = a[i - n2];
            }
            for (int i = 0; i < n; i++) {
                int il = i - 1, ir = i + 1;
                if (il < 0)il = n - 1;
                if (ir >= n)ir = 0;
                if (b[i] > b[il] && b[i] > b[ir])continue;
                if (b[i] < b[il] && b[i] < b[ir])continue;
                flag = false;
                break;
            }
            if (flag) {
                cout << "YES\n";
                for (int i = 0; i < n; i++)cout << b[i] << ' ';
                cout << '\n';
                continue;
            }
            flag = true;
            cnt = 0;
            for (int i = 0; i < n; i++) {
                b[cnt++] = a[i];
                if (i + n2 >= n)break;
                b[cnt++] = a[i + n2];
            }
            for (int i = 0; i < n; i++) {
                int il = i - 1, ir = i + 1;
                if (il < 0)il = n - 1;
                if (ir >= n)ir = 0;
                if (b[i] > b[il] && b[i] > b[ir])continue;
                if (b[i] < b[il] && b[i] < b[ir])continue;
                flag = false;
                break;
            }
            if (flag) {
                cout << "YES\n";
                for (int i = 0; i < n; i++)cout << b[i] << ' ';
                cout << '\n';
                continue;
            }
            cout << "NO\n";
        }
     
    }

 

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

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