Codeforces Global Round 19 1663 -> 1589

https://codeforces.com/contest/1634

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

 

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

 

A. Sorting Parts

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

Problem - A - Codeforces

문제

 

n길이로 이루어진 배열 a가 있다. len을 골라서 앞에서부터 len개를 오름차순으로 정렬하는 operation이 있을 때 원하는 len을 골라 1번 실행한 후에 a가 오름차순으로 정렬되지 않은 상태를 만들 수 있는지 출력하는 문제

 

풀이

 

처음부터 모두 정렬되있으면 답은 NO 이외에는 YES이다

 

 

코드

 

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

 

 

B. MEX and Array

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

Problem - B - Codeforces

문제

 

n개의 수가 있는 a 배열에서 모든 subarray중에 각각의 subarray에서 그룹을 골라 c + MEX(각 그룹) 의 최대 값들을 더하여 계산하는 문제 여기서 c는 그룹의 개수

 

풀이

 

그룹의 길이를늘려 MEX값을 1키우는 거나 그룹의 개수를 늘려 c의 값을 1 키우는거나 똑같기 때문에 그룹을 최대로 늘려서 계산하는것이 이득이 된다. 고로 각 subarray의 최대 그룹수 의 식을 더해주면 된다.

 

코드

 

    #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 = 1; i <= n; i++)cin >> a[i];
            for (int l = 0; l <= n; l++) {
                for (int i = 1; i <= n; i++) {
                    int i2 = i + l;
                    if (i2 > n)break;
                    int cnt = 0;
                    for (int j = i; j <= i2; j++) {
                        if (a[j] == 0)cnt++;
                    }
                    ans += (l + 1) + cnt;
                }
            }
            cout << ans << '\n';
        }
    }

C. Andrew and Stones

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

Problem - C - Codeforces

문제

 

n개의 돌더미가 있다. i번째 돌더미에는 a[i]개의 돌이 있고 아래의 operation을 원하는 만큼 했을 때 1번째와 n번째로 돌을 다 옮길 수 있으면 최소값을 출력하고 못옮긴다면 -1을 출력하는 문제

1. i,j,k (i<j<k) , a[j]>=2인 돌들을 골라 j번째 돌을 2개 없애고 좌측과 우측에 1개씩 옮기는 operation

 

풀이

 

2~n-1 번째 돌더미중에 하나라도 2이상인게 있으면 가능하고 최소값은 a[i]/2 + a[i]의 홀수 갯수 ( i = 2~(n-1) ) 이고 이외에는 답은 -1이다. 다만 n=3일때는 2번째가 홀수이면 안된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    long long 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;
            long long ans = 0;
            for (int i = 1; i <= n; i++) {
                cin >> a[i];
            }
            if (n == 3) {
                if (a[2] % 2)cout << -1 << '\n';
                else cout << a[2] / 2 << '\n';
                continue;
            }
            bool flag = false;
            for (int i = 2; i < n; i++) {
                if (a[i] > 1) {
                    flag = true;
                    break;
                }
            }
            if (flag == false) {
                cout << -1 << '\n';
                continue;
            }
            for (int i = 2; i < n; i++) {
                if (a[i] % 2) {
                    ans += (a[i] + 1) / 2LL;
                }
                else ans += a[i] / 2LL;
            }
            cout << ans << '\n';
           
        }
    }

 

 

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

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