백준 및 코드포스

A. XOR Mixup

n - 1 개의 정수를 모두 xor연산한 숫자가 추가된 후 n개의 정수를 섞었을 때, 추가된 하나의 숫자를 찾는 문제입니다.

그냥 n개 중에 아무 숫자나 출력하면 정답입니다.

#include <stdio.h>
using namespace std;
int main() {
int n, m;
int t;
scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%d", &m);
        }
        printf("%d\n", m);
    }
}

B. Rising Sand

 1 < 𝑖 < 𝑛 인 동시에 𝑎𝑖 > 𝑎𝑖−1 + 𝑎𝑖+1 인 모든 i번째 모래 더미는 too tall 이라고 합니다.

k개의 연속된 모래 더미의 크기를 동시에 1씩 무한 번 추가할 수 있을 때, 만들 수 있는 too tall 모래 더미의 개수를 출력하면 됩니다.

k가 1이라면 원하는 모래더미만 골라서 크기를 키울 수 있기 때문에

하나 건너 하나씩 too tall하게 만들 수 있습니다.

k가 1 일 경우 정답은 (n - 1) / 2

k가 2 이상인 경우 이미 too tall 하지 않을 경우 too tall 하게 만들 수 없습니다.

기존의 too tall 한 모래 더미의 수를 세어주면 정답입니다.

#include <stdio.h>
int main() {
int n, m;
int arr[1000000] = {};
int t;
scanf("%d", &t);
    while(t--) {
        int count = 0;
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }
        for(int i = 1; i < n - 1; i++) {
            if(arr[i] > arr[i - 1] + arr[i + 1]) count++;
        }
        if(m == 1) {
            count = (n - 1) / 2;
        }
        printf("%d\n", count);
    }
}

C. 3SUM Closure

arr[i] + arr[j] + arr[k] 의 값이 배열에 없을 경우 NO, 모든 경우에서 있을 경우 YES를 출력해주면 됩니다.

양수가 3개 이상이면 양수끼리 3개를 더할 경우 무조건 더해진 3개의 양수의 값보다 더 큰 양수가 나오기 때문에 무조건 no 입니다.

음수가 3개 이상일 경우에도 마찬가지입니다.

0은 10000개가 있으나 3개가 있으나 결과가 동일하므로 0의 개수가 3 이상일 경우 3으로 퉁쳐주었습니다.

그리고 남은 값들 끼리 브루트포스를 돌려주면 됩니다.

#include <stdio.h>
int main() {
int n, m;
int arr[1000000] = {};
int ans[10] = {};
int t;
scanf("%d", &t);
while(t--) {
    int plus = 0, minus = 0, zero = 0, one = 0, no = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        if(arr[i] > 0) plus++;
        else if(arr[i] < 0) minus++;
        else if(arr[i] == 0) zero++;
    }
    if(plus > 2) no = 1;
    else if(minus > 2) no = 1;
 
    else {
        for(int i = 0; i < n; i++) {
            if(arr[i] > 0 || arr[i] < 0) {
                ans[one] = arr[i];
                one++;
            }
        }
        if(zero > 3) zero = 3;
        for(int i = 0; i < zero; i++) {
            ans[one] = 0;
            one++;
        }
        for(int i = 0; i < one; i++) {
            for(int j = i + 1; j < one; j++) {
                for(int k = j + 1; k < one; k++) {
                    no = 1;
                    for(int z = 0; z < one; z++) {
                        if(ans[i] + ans[j] + ans[k] == ans[z]) no = 0;
                    }
                    if(no == 1) goto E;
                }
            }
        }
    }
    E:
    if(no) printf("NO\n");
    else printf("YES\n");
 
}
}

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