Codeforces Round #772 (Div. 2) 1646 -> 1670

https://codeforces.com/contest/1635

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

 

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

 

A. Min Or Sum

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

Problem - A - Codeforces

 

문제

 

n길이의 배열 a가 있다. 두개의 인덱스 i,j를 골라 a[i]는 x로 a[i]는 y로 교체할 수 있다. 하지만 a[i] | a[j] = x|y 여야한다.

이때 배열 합의 최소를 구하는 문제

 

풀이

 

OR은 최대로 할수록 합이 최소가 되니까 모두 OR해서 출력한다.

 

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    long long a[101];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            int n;
            cin >> n;
            long long ans = 0;
            for (int i = 0; i < n; i++) {
                cin >> a[i];
                ans |= a[i];
            }
            cout << ans << '\n';
        }
    }

 

B. Avoid Local Maximums

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

Problem - B - Codeforces

문제

 

n길이의 배열 a가 있다. 각 요소는 1~10e9 사이이며 원하는만큼 operation을 할 수 있는데 operation은 아래와 같다.

operation : 1부터 10e9 사이의 정수중 아무거나 바꾼다.

이때 a[i]> a[i-1] and a[i] > a[i+1]인 local maximum 요소가 없게 하기 위한 최소한의 operation과 그러한 배열을 출력하는 문제

 

풀이

 

a[i]를 기준으로 만약 a[i-1]과 a[i+1]이 local maximum 이라면 max(a[i-1],a[i+1])로 바꿔줌으로써 두개의 local maximum을 없앨 수 있고 이러한 a[i]가 없다면 각 local maximum을 1개씩 없애면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    long long a[200001];
    bool check[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];
                check[i] = false;
            }
            int ans = 0;
            for (int i = 2; i < n; i++) {
                if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
                    check[i] = true;
                }
            }
            for (int i = 2; i < n; i++) {
                if (check[i - 1] && check[i + 1]) {
                    a[i] = max(a[i - 1], a[i + 1]);
                    check[i - 1] = check[i + 1] = false;
                    ans++;
                }
            }
            for (int i = 2; i < n; i++) {
                if (check[i]) {
                    a[i] = max(a[i - 1], a[i + 1]);
                    ans++;
                }
            }
            cout << ans << '\n';
            for (int i = 1; i <= n; i++)cout << a[i] << ' ';
            cout << '\n';
        }
    }

 

C. Differential Sorting

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

Problem - C - Codeforces

문제

 

n길이의 배열 a가 있다. x,y,z (1<=x <y<z<=n)을 골라 a[x] = a[y]-a[z] 연산을 최대 n번 수행할 수 있을 때 non-decreasing 배열로 만들 수 있으면 각 x,y,z 연산을 출력하고 아니라면 -1을 출력하는 문제

 

풀이

 

가장 끝 원소 2개는 연산으로 바꿀 수 없으므로 무조건 a[n-1] < a[n]을 만족해야하고  a[n]이 음수라면 처음부터 정렬이 되어있어야 한다. a[n]>=0이라면 y , z를 a[n-1]과 a[n]으로 무조건 정렬할 수 있고 이외에는 연산으로 정렬을 못한다.

 

코드

 

    #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];
            if (a[n] < a[n - 1]) {
                cout << -1 << '\n';
                continue;
            }
            bool flag = true;
            for (int i = 2; i <= n; i++) {
                if (a[i - 1] > a[i]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                cout << 0 << '\n';
                continue;
            }
            // 이제부터 무조건 맨뒤에숫자가 더 크다
            
            if (a[n] < 0) {
                cout << -1 << '\n';
                continue;
            }
            cout << n - 2 << '\n';
            for (int i = 1; i <= n - 2; i++) {
                cout << i << ' ' << n - 1 << ' ' << n << '\n';
            }
        }
    }

 

 

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

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