Codeforces Round #618 (Div. 2)

문제 링크 : https://codeforces.com/contest/1300

 

A. Non-zero

문제 요약

입력된 배열을 모두 곱하거나 더해도 0이 되지 않도록 하게 만드는 최소 횟수를 출력하는 문제이다.

 

접근 방법

입력에 0이 있으면 곱해서 0이 되므로 0이 있는 만큼 카운트를 해주고, 더했을 때 0이 되면 1만큼 카운트를 해준다.

 

시간복잡도

O(n)

#include <bits/stdc++.h>

using namespace std;
 
int main(void) {
    int c;
    cin >> c;
    while(c--) {
        int n;
        cin >> n;
        int ret = 0, sum = 0;
        for(int i = 0; i < n; i++) {
            int input;
            cin >> input;
            sum += input;
            if(input == 0) {
                ret++;
                sum++;
            }
        }
        if(sum == 0) ret++;
        printf("%d\n", ret);
    }
    
    return 0;
}

 

B. Assigning to Classes

문제 요약

어떠한 2n 길이의 배열이 주어질 때, 홀수 개의 두 배열로 쪼개서 두 배열의 중간값(Median)이 최소가 되는 값을 출력하는문제이다.

 

접근 방법

[0...2n-1]의 배열에서 중간값인 [n-1], [n]을 두 배열에 각각 넣고, 각 배열 양 쪽에 [0...n-2], [n+1, 2n-1]을 하나씩 각 배열에 번갈아서 넣으면 될 것 같았다.

 

시간복잡도

정렬하는 데 O(n log n)이 걸린다.

#include <bits/stdc++.h>

using namespace std;
 
int main(void) {
    int c;
    cin >> c;
    while(c--) {
        int n;
        cin >> n;
        vector<int> V(2*n);
        for(int i = 0; i < 2*n; i++) {
            cin >> V[i];
        }
        sort(V.begin(), V.end());
        printf("%d\n", abs(V[n-1]-V[n]));
    }
    
    return 0;
}

 

C. Anu Has a Function

문제 요약

정수 배열이 주어질 때, 배열의 처음부터 두 수를 차례대로 함수를 적용시킨 후의 출력값이 최대가 되려면 배열의 데이터를 어떻게 배치해야 하는지에 관한 문제이다.

 

접근 방법

f(x, y) = (x|y)-y 를 정리하면 f(x,y) = x&~y 이므로, 문제에서 말하는 대로 적용하면 V[0] & ~V[1] & ... & ~V[n-1]이다.

처음 값을 제외하고 모두 NOT 연산을 한 후 전체를 AND 연산한다는 뜻이고,

V[0]은 V[1...n-1]의 k번째 자리의 비트가 0일 때, 1이어야 한다는 뜻이다. (그래야 NOT 연산을 했을 때 1이 되므로)

이렇게 되었을 때 가장 큰 값을 가지는 V[i]를 찾고, 이 값을 제일 처음으로 출력하면 된다.

그리고 메모이제이션을 적용하기 위해 두 배열 l, r을 만들었다.

 

시간복잡도

l, r 배열을 만드는데 O(n)

#include <bits/stdc++.h>

using namespace std;
 
int main(void) {
    int c;
    cin >> c;
    vector<int> V(c);
    for(int i = 0; i < c; i++) {
        cin >> V[i];
    }
    
    vector<int> l(c); //l[i]=~V[0]&...&~V[i-1]
    vector<int> r(c); //r[i]=~V[n-1]&...&~V[i+1]
    l[0]=r[c-1]=(1<<31)>>31;
    
    for(int i = 1; i < c; i++) {
        l[i] = l[i-1] & ~V[i-1];
    }
    for(int i = c-2; i >= 0; i--) {
        r[i] = r[i+1] & ~V[i+1];
    }
    
    int m = -1, sum = -1;
    for(int i = 0; i < c; i++) {
        if(sum < (l[i] & r[i] & V[i])) {
            sum = l[i] & r[i] & V[i];
            m = i;
        }
    }
    
    printf("%d ", V[m]);
    for(int i = 0; i < c; i++){
        if(i == m) continue;
        printf("%d ", V[i]);
    }
    
    return 0;
}

 

총평

스터디에서 D번 문제는 나 빼고 다 풀었는데 난 이해가 되지 않았다. 다른 사람들이 해설한 걸 다시 보니 이해가 되긴 하는데 내가 이 방법을 생각할 수 있도록 노력해야겠다.