Codeforces Round #796 (Div. 2) 1681 → 1673

https://codeforces.com/contest/1688

https://codeforces.com/contest/1688

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

 

A. Cirno's Perfect Bitmasks Classroom

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

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

문제

 

양의 정수 x가 주어진다. 아래의 조건에 맞는 최소 y를 출력하는 문제

 

1. x and y>0

2. x xor y>0

 

풀이

 

x와 겹치는 최소 비트를 찾아 정답에 더해주고, 아래의 조건을 만족한다면 그대로 출력, 아니라면 x가 가지지 않는 최소 비트를 하나 더 찾아서 출력해주면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
     
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
     
        int T;
        cin >> T;
        while (T--) {
            long long x;
            cin >> x;
            long long ans = 0;
            for (int i = 0; i < 33; i++) {
                if ((x & (1LL << i))) {
                    ans += (1LL << i);
                    break;
                }
            }
            if ((x ^ ans) > 0) {
                cout << ans << '\n';
                continue;
            }
            for (int i = 0; i < 33; i++) {
                if ((x & (1LL << i)) == 0) {
                    ans += (1LL << i);
                    break;
                }
            }
            cout << ans << '\n';
        }
    }

 

B. Patchouli's Magical Talisman

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

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

문제

 

n길이의 배열 a가 주어진다. 아래 두가지중 한번에 하나의 operation을 수행할 수 있고 모든 원소를 홀수로 만들기 위한 최소 operation을 출력하는 문제

1. 합체 : 두개의 원소를 골라 제거하고 두 원소의 합을 추가한다

2. 축소 : 짝수 원소를 골라 2로 나누어 준다.

 

풀이

 

홀수가 하나라도 있다면 답은 짝수의 개수(더하면 되므로), 하나도 없다면 한 원소를 홀수로 만들기 위한 최소 operation수 + (n-1)을 더해서 출력해주면 된다.

 

코드

 

    #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;
            int odd = 0, even = 0;
            for (int i = 0; i < n; i++) {
                cin >> a[i];
                if (a[i] % 2)odd++;
                else even++;
            }
            if (odd) {
                cout << even << '\n';
            }
            else {
                int MIN = 300;
                for (int i = 0; i < n; i++) {
                    int cnt = 0;
                    while (a[i] % 2 == 0) {
                        a[i] /= 2;
                        cnt++;
                    }
                    MIN = min(cnt, MIN);
                }
                cout << (n - 1) + MIN << '\n';
            }
        }
    }

D. The Enchanted Forest

https://codeforces.com/contest/1688/problem/D

https://codeforces.com/contest/1688/problem/D

문제

 

n길이의 숲에 버섯이 심어져 있다. 숲은 1차원 좌표로 나타나고 i번째 위치에는 a[i]개의 버섯이 있다. 0초에 원하는 위치에 가서 각 초마다 각 위치에 있는 버섯을 얻을 수 있고 1초에 모든 자리에 1개의 버섯이 새로 자라나서 증가한다. 이때 k가 주어지고 k초에 얻을 수 있는 최대 버섯의 수를 출력하는 문제

 

풀이

 

새로 자라나는 버섯은 따로 계산하여 구해주고 k가 n길이 미만이라면 k길이 중에서 가장 합이 큰 구간을 구해서 계산하여 출력해주고 n 길이 이상이라면 한 지점에 쭉 대기하다가 나머지를 일자로 쓸어가는 방법을 계산하여 출력해주면 된다.

 

코드

    #include <bits/stdc++.h>
    using namespace std;
    long long a[200001];
    long long psum[200001];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
     
        int T;
        cin >> T;
        while (T--) {
            long long n,k;
            cin >> n>>k;
            for (int i = 1; i <= n; i++) {
                cin >> a[i];
                psum[i] = psum[i - 1] + a[i];
            }
            long long sum = 0;
            if (k >= n) {
                for (int i = 1; i <= n; i++)sum += a[i];
                long long dif = k - (n - 1);
                sum += (dif - 1);
                sum += (k * (k - 1)) / 2LL;
                sum -= (dif * (dif - 1LL)) / 2LL;
                cout << sum << '\n';
            }
            else {
                long long MAX = 0;
                for (int i = k; i <= n; i++) {
                    MAX = max(MAX, psum[i] - psum[i - k]);
                }
                sum += (k * (k - 1)) / 2LL;
                long long ans = MAX + sum;
                cout << ans << '\n';
     
            }
        }
    }

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

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