백준 및 코드포스

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");
 
}
}

아 진짜 아쉽네요 E에서 뭐가 틀린 건지 한참 헤멨는데 int를 long long으로 바꾸니까 바로 AC 받았습니다.

그것만 신경 써줬으면 1350 정도 퍼포 나왔을텐데 진짜 아쉽네요..

세네판 정도 안에 그린 찍고 싶었는데 ㅋㅋ 안 될 것 같네요

A. Print a Pedestal (Codeforces logo?)

가운데가 제일 길쭉하고 왼쪽이 그 다음, 오른쪽이 그다음으로 길도록 해주는 단순 구현 문제입니다.

#include <stdio.h>

int main() {
int n, t;
scanf("%d", &t);
while(t--) {
    scanf("%d", &n);
    int first = n / 3 + 1;
    if(n % 3 != 0) first++;
    int second = n - first;
    second /= 2;
    second++;
    int third = n - first - second;
    printf("%d %d %d\n", second, first, third);
}
}

B. Array Decrements

이번 코포는 B 때문에 망했다고 해도 과언이 아닌..

#include <stdio.h>

int main() {
int n,m, t;
int arr[1000000] = {};
int brr[1000000] = {};
scanf("%d", &t);
while(t--) {
    scanf("%d", &n);
    int temp = 0,NO = 0,no = 0;
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &brr[i]);
        if(arr[i] < brr[i]) NO = 1;
    }
    for(int i = 0; i < n; i++) {
            if(temp < arr[i] - brr[i]) temp = arr[i] - brr[i];
    }
    if(temp == 0) temp = arr[0] - brr[0];
    for(int i = 0; i < n; i++) {
        arr[i] -= temp;
    }
    for(int i = 0; i < n; i++) {
        if(arr[i] != brr[i]) {
            no++;
            if(brr[i] == 0 && arr[i] <= 0) no--;
        }
    }
    if(no || NO) printf("NO\n");
    else printf("YES\n");
}
}

이렇게 어렵게 푸는 것도 맞는지도 모르겠습니다 사실..

여태 코포 몇판 안 해봤지만 중간에 문제 하나 막히면 거기서 말리기 시작하는 타입인 거 같아요 저는

일 끝나기 전에 다음 task 주면, task 끝낸 시간의 간격 출력.

일 끝나고 난 후에 다음 task 주면 task 준 시간과 끝낸 시간의 간격 출력.

푸는 데에 5분도 안 걸렸습니다.

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

D. Black and White Stripe

문자열에서 0~k-1 의 문자열 안에 W가 얼마나 들어있는지 찾고

앞으로 한 칸씩 나가면서 가장 적은 값 출력.

엄청 쉬운 문제인데 구현 실수해서 2번이나 틀렸습니다.

근데 이건 제 실력이 부족한 탓이에요

#include <stdio.h>
#include <algorithm>

int main() {
int n,m, t;
char s[300000] = {};
scanf("%d", &t);
while(t--) {
 scanf("%d", &n);
 scanf("%d", &m);
 scanf("%s", s);
 int count = 0, min = 10000000;
 for(int i = 0; i < m; i++) {
     if(s[i] == 'W') count++;
 }
 if (min > count) min = count;
 for(int i = 0; i < n - m; i++) {
     if(s[m + i] == 'W') count++;
     if(s[i] == 'W') count--;
     if(min > count) min = count;
 }
 printf("%d\n", min);
}
}

E. Price Maximization

맨 처음에 각각 물건 입력받으면서 k로 나눈 값 더해주고,

나머지는 모아서 배열에 담은 다음에 작은놈들끼리 짝지어주면서 짝 맞으면 더해주는 식으로 짰습니다...

구현까지도 괜찮았는데 long long을 쓰는 걸 깜빡했네요

𝑎𝑛은 10억까지도 가능하니까 당연히 long long인데 이걸 뭔 생각으로 int로 출력하려 했는지..  앞으로 

#define int long long 쓰겠습니다 짜증나서..

#include <stdio.h>

int main() {
int n,m, t;
int k[1001] = {};
scanf("%d", &t);
while(t--) {
    scanf("%d%d", &n, &m);
    long long temp = 0;
    long long ans = 0;
    for(int i = 0; i < n; i++) {
        scanf("%lld", &temp);
        ans += temp / m;
        k[temp % m]++;
    }

    int end = m, first = 1;
    
    for(int i = 0; i <= m; i++) {
        for(int j = m - i; j <= m; j++) {
                if(i == j) {
                    ans+= k[i] / 2;
                    k[i] %= 2;
                    continue;
                }
                if(k[i] > 0 && k[j] > 0) {
                if(k[i] > k[j]) {
                    int temp = k[j];
                        ans += k[j];
                    k[i] -= temp;
                    k[j] -= temp;
                }
                else {
                    int temp = k[i];
                    ans += k[i];
                    k[i] -= temp;
                    k[j] -= temp;
                }
                                    //printf("%d %d\n", k[i], k[j]);
            }
        }
    }
    for(int i = 0; i < 1000; i++) {
        k[i] = 0;
    }
    printf("%lld\n" , ans);
}
}

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