Codeforces Round #796 (Div. 2) A, B ,D 풀이

https://codeforces.com/contest/1688

https://codeforces.com/contest/1688

3솔 했습니다.

C는 못 풀었습니다.

A. Cirno's Perfect Bitmasks Classroom

x를 주면 x & y가 0보다 크고 x ^ y가 0보다 큰 y의 최솟값을 출력해주면 됩니다.

2^30부터 2^0까지 2씩 나눠주면서,
x가 해당값보다 더 크거나 같다면 차례대로 빼주다가 x가 0이 된다면 그 값을 출력해주면 됩니다.
근데 숫자를 한 번만 빼줬는데 0이 된다면 +1을 (64 - 64 = 0 의 경우 65를) 출력해주면 됩니다.
그리고 x가 1일 경우 y는 3입니다.

B. Patchouli's Magical Talisman

순열에서 2개를 골라 합치거나, 절반으로 나누는 과정을 최소로 하여 순열의 모든 값이 홀수가 되는 최소 연산 수를 출력해주면 됩니다.

1. 홀수가 하나라도 있으면 홀수 + 짝수는 홀수니까, 짝수가 있을 때마다 홀수랑 합쳐주면 되겠죠.
짝수가 등장한 횟수를 출력합니다.
2. 모두 짝수라면 짝수를 각각 홀수가 될 때까지 2로 나눠보면서 그 중 가장 연산이 적었던 수의 연산 횟수 + 짝수의 개수 - 1을 출력합니다.

c는 모르겠더라구요.

D. The Enchanted Forest

값이 1분에 1씩 커지는 마법의 숲에서 수확할 수 있는 버섯의 최댓값을 구하는 문제입니다.

배열 전체에 1씩 더하는 연산을 해주기엔 K값이 최대 10억까지 가능하기 때문에 TLE가 납니다.

1. n보다 k가 더 작다면 총합의 값이 가장 큰 구간을 구해줍니다.
2. k가 n보다 크거나 같다면 배열의 값을 전부 다 더해줍니다.
3. (k - n) ~ (k - 1) 까지 더한 값을 앞의 값에 더해 출력합니다.

2와 같이 계산해주는 이유는 마지막에 배열의 첫번째부터 마지막까지 쭉 쓸어주면서 값을 더해주는게 최댓값이기 때문입니다.
어차피 마지막에 버섯이 자란만큼 전부 수확해줄 거라면 그 이전에 어디서 어떻게 움직였든 상관없이, 마지막에 일직선으로 한 번 훑어주기만 하면 됩니다.

#include <stdio.h>
int main() {
    int t,a,b;
    int arr[1000000] = {};
    scanf("%d", &t);
    while(t--) {
        long long sum = 0;
        long long max = 0;
        scanf("%d %d", &a, &b);
        for(int i = 0; i < a; i++) {
            scanf("%d", &arr[i]);
        }
        if(b < a) {
            for(int i = 0; i < b; i++) {
                sum+= arr[i];
                if(max < sum) max = sum;
            }
            for(int i = 0; i < a - b; i++) {
                sum-=arr[i];
                sum+=arr[b+i];
                if(max < sum) max = sum;
            }
            for(int i = 0; i < b; i++) {
                max += i;
            }
        }
        else {
            for(int i = 0; i < a; i++) {
                max+=arr[i];
            }
            for(int i = b-a; i < b; i++) {
                max += i;
            }
        }
        printf("%lld\n", max);
    }
}

D는 풀기에 재밌었습니다. Enchanted forest라는 제목도 맘에 듭니다.
https://www.adultswim.com/videos/smiling-friends/enchanted-forest

Watch Smiling Friends Episodes Free from Adult Swim

Smiling friends 에피소드 중에 하나인데 진짜 재밌습니다.
A는 재미없었고 B도 좋았던 것 같습니다.