백준 및 코드포스

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

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

3솔 했습니다.
C까지의 난이도가 쉬운편이라 속도경쟁만 됐네요.
D 푼 사람이 360명이고 E F는 각각 6, 4명이 풀었습니다 흠..

다행히 전 빠르게 풀어서 2200등으로 최고기록 달성했습니다.
https://codeforces.com/contest/1686

A. Everything Everywhere All But One

문제
배열에서 한 개의 원소만 선택하지 않고 나머지를 모두 골라서 평균을 만들었을 때 모든 수의 값이 똑같아질 수 있는지 판단

해결
한 개의 원소의 값 == 나머지 모든 원소의 평균 이 성립하려면, 결국 모든 원소의 평균이 한 개의 원소의 평균과 같아야한다는 뜻입니다.
원소의 값을 전부 더해준 다음 n으로 나눠서 배열 중에 있다면 YES 아니라면 NO

#include <stdio.h>
int main() {
    int t;
    int arr[100000] = {}, brr[100000] = {};
    scanf("%d", &t);
    while(t--) {
        int n,m;
        double sum = 0;
        scanf("%d", &n);
        for(int i = 0; i < n;i++) {
            scanf("%d", &arr[i]);
            sum += arr[i];
        }
        int yes = 0;
        double avg = sum / n;
        for(int i = 0; i < n; i++) {
            if(arr[i] == avg) yes = 1;
        }
        if(yes) printf("YES\n");
        else printf("NO\n");
    }
}

B. Odd Subarrays

무슨 말인지 이해가 안 가서 번역기 돌렸더니, 번역기도 이상하게 번역을 해서 번역에 시간을 한참 쓴 문제입니다.
앞에 있는 원소의 값이 뒤에 있는 원소의 값보다 큰 쌍의 개수가 홀수면 odd라고 할 때, odd인 경우가 최대가 되도록 배열을 나눠주라는 문제입니다.
[4 3 2 1] 의 경우 [4,3] [2,1]로 나누면 각각 1개, 1개로 odd가 2가 되겠죠.

그리디하게 앞에서부터 읽어나가면서 뒤의 원소의 값이 바로 앞의 원소의 값보다 작다면 횟수를 세어주고 한 칸 건너뛰는 식으로 코드를 작성했습니다.

#include <stdio.h>

int main() {
    int t;
    int arr[300000] = {};
    scanf("%d", &t);
    while(t--) {
        int n,m;
        int sum = 0;
        scanf("%d", &n);
        for(int i = 0; i < n;i++) {
            scanf("%d", &arr[i]);
        }
        for(int i = 0; i < n-1; i++) {
            if(arr[i] > arr[i + 1]) {
                sum++;
                i++;
            }
        }
        printf("%d\n", sum);
    }
}

C. Circular Local MiniMax

• 𝑏𝑖−1<𝑏𝑖>𝑏𝑖+1
• 𝑏𝑖−1>𝑏𝑖<𝑏𝑖+1이렇게 2가지 조건을 만족하는 원순열로 만들 수 있는지 판단하고, 가능하다면 그 순열을 출력하는 식입니다.

시간이 가장 오래 걸린 문제입니다.
n이 홀수일 경우 어떻게 만들 수 있다고 판단해서 시간을 오래 썼습니다.
하지만 홀수일 경우 아예 만들 수 없습니다.
짝수일 경우 sort 후
작은 값 큰 값 작은 값 큰 값 작은 값 큰 값
으로 반복해서 다른 배열 brr에 저장해보고, for문으로 위의 조건을 확인하는지 체크해준 후, 이상이 없으면 brr배열 그대로 출력해주는 방식으로 풀었습니다.

2 1 5 2 3의 경우
2 1 5 2 3 2... 이 되니까 3도 양 옆보다 크고, 그래서 참인 줄 알았습니다.
알고보니
2 1 5 2 3 2 1이 돼서 2가 오른쪽엔 1, 왼쪽엔 3을 두고 있어서 조건을 만족하지 못한단 점을 모르고 코드를 작성해서 1번 WA 받았습니다..

해석에도 시간을 너무 오래 썼고, 순위는 역대급이지만 여러모로 아쉬운 대회네요.

#include <stdio.h>
#include <algorithm>
#include <string.h>
int main() {
    int t;
    int arr[300000] = {}, brr[300000] = {};
    scanf("%d", &t);
    while(t--) {
        int n,m;
        int sum = 0, count = 0, no = 0;
        scanf("%d", &n);
        for(int i = 0; i < n;i++) {
            scanf("%d", &arr[i]);
        }
        std::sort(arr,arr+n);
        int one = 0;
         if(n % 2 == 0) {
            for(int i = 0; i < n / 2; i++) {
                   brr[one] = arr[i];
                   one++;
                   brr[one] = arr[n / 2 + i];
                   one++;
            }
        }
        else {
            one = 0;
            for(int i = 0; i < n / 2; i++) {
               brr[one] = arr[n/2 + i];
               one++;
               brr[one] = arr[i];
               one++;
            }
            brr[one] =  arr[n - 1];
            one++;
        }
        brr[one] = brr[0];
        if(n%2 == 0) {
                for(int i = 0; i < n; i++) {
                if(i % 2 == 0 && brr[i] >= brr[i + 1]) no = 1;
                if(i % 2 == 1 && brr[i] <= brr[i + 1]) no = 1;
            }
        }
        else {
            for(int i = 0; i < n; i++) {
                if(i % 2 == 1 && brr[i] >= brr[i + 1]) no = 1;
                if(i % 2 == 0 && brr[i] <= brr[i + 1]) no = 1;
            }
        }
            if(n % 2 == 1 || no == 1) printf("NO\n");
            else {
                printf("YES\n");
            for(int i = 0; i < n; i++) {
                    printf("%d ", brr[i]);
            }
            printf("\n");
            }
        //if(count > n / 2) printf("NO\n");
        //else if(n < 4) printf("NO\n");
 
    }
}
//2 1 5 2 3
//4 1 5 2 3
//1 5 2 6 1 2

https://www.acmicpc.net/problem/4344

#include <stdio.h>
int main() {
    double C, n;
    double arr[1000] = {}; //최소 1~ 최대 1000명이니, 1000칸만 있으면 됩니다.
    scanf("%lf", &C);
    for(int i = 0; i < C; i++) { //C번만큼 반복
        double sum = 0; //총 합계
        scanf("%lf", &n);

        for(int j = 0; j < n; j++) {
            scanf("%lf", &arr[j]);
            sum += arr[j]; //배열에 입력해주며 총 합계를 구해줍니다.
        }
        
        double average = sum / n; // 평균 = (총합) / (명 수)
        double over = 0;//평균을 넘는 사람을 세줄 변수 선언
        for(int j = 0; j < n; j++) {
            if(arr[j] > average) { //배열에 담긴 점수가 평균을 넘으면
                over++; //over에 +1
            }
        }
        printf("%.3lf%%\n", (over/ n) * 100);
    }
}

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

3솔 했습니다.

A. Game with Cards

각자 카드를 번갈아서 내는데, 방금 상대방이 낸 것보다 숫자가 큰 카드를 내야합니다.

Alice가 먼저 카드를 내면 누가 이기는지, Bob이 먼저 카드를 내면 누가 이기는지 출력해주면 됩니다.

각자 제일 큰 카드의 값이 같다면, 먼저 내는 애가 이기고(더 큰 카드를 낼 수 없으니까)

아니라면 상대방보다 더 큰 카드를 갖고 있는 애가 무조건 이깁니다.

B. Card Trick

카드 뭉치 위에서 b장을 뽑아서 밑으로 내리는 작업을 m번 했을 때, 가장 위에 오는 카드의 번호를 출력하는 문제입니다.

배열로 카드 원소를 각각 입력받고, 밑으로 내리는 카드 b장을 다 더해서 카드의 총 장수로 나머지 연산을 하면 됩니다.

 ex) [1,2,3,4,5] 5장이라고 가정, 위에서부터 2, 3, 2개 내리는 작업을 했다면 7 % 5 => 2, arr[2] = 3 이런 식입니다.

#include <stdio.h>

int main() {
    int t;
    scanf("%d", &t);
    int arr[300000] = {}, brr[300000] = {};
    while(t--) {
        int n, m;
        int alice = 0, bob = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }
        scanf("%d", &m);
        int temp, sum = 0;
        for(int i = 0; i< m ; i++) {
            scanf("%d", &temp);
            sum += temp;
            while(sum >= n) {
                sum -= n;
            }
        }
        printf("%d\n", arr[sum]);
    }
}

C. Double Sort

이거는 2행짜리 배열에서 i열, j열을 골라서 값을 바꿀 때,

각 행이 non-decreasing 하게 정렬이 될 수 있는지,

된다면 몇번 바꿔야 하는지, 그리고 그 바꿀 때의 i와 j를 출력해줘야 하고,

못 바꾸거나 바꿔야하는 횟수가 1만회 넘어가면 -1 출력.

이건 그냥 구현입니다.

이중 for문에서

arr[i] > arr[j] && brr[i] < brr[j] 인 경우나

arr[i] < arr[j] && brr[i] > brr[j] 인 경우가 한 개라도 있으면 -1 출력.

아니라면 arr기준으로 먼저 정렬해주고 그 다음에 brr 기준으로 정렬 해줬습니다.

값이 중복될 경우 정렬이 안 될 수 있기에 나눠서 두번 해줬습니다.

ex)

arr [1,1,1,1,1]

brr[5,4,3,2,1]  인 경우 arr만 정렬하거나 혹은 거꾸로인데 brr만 정렬하면 정렬이 안되니까...