Good Bye 2019

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

 

A. Card Game

문제 요약

숫자가 적혀 있는 N개의 카드(1~N, 중복 없음)로 카드 게임을 하는데, 카드 패에 따른 승자를 출력하는 문제이다.

 

접근 방법

결국 승자는 제일 높은 수가 적힌 카드를 가진 사람이므로, N을 누가 가지고 있는지 체크하여 문제를 풀면 된다.

 

시간복잡도

입력을 받으면서 확인을 했으니, O(n)이라고 해야할지 O(1)이라고 해야할지 모르겠지만, O(n)이 맞는 것 같다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(void) {
    int test_cases;
    cin >> test_cases;
    for(int i = 0; i < test_cases; i++) {
        int n, a, b;
        scanf("%d %d %d", &n, &a, &b);
        bool ret = false;
        for(int i = 0; i < n; i++) {
            int temp;
            scanf("%d", &temp);
            if(temp == n) {
                if(i < a) ret = true;
            }
        }
        cout << (ret ? "YES" : "NO") << endl;
    }
    
    return 0;
}

 

B. Interesting Subarray

문제 요약

임의의 정수 배열 A가 있다고 할 때, A[i...j]의 최댓값과 최솟값의 차가 subarray의 갯수 k보다 크거나 같은지를 확인하고 답이 있으면 그 답을 출력하는 문제이다.

 

접근 방법

처음엔 각 subarray의 Max와 Min을 계산하려고 했는데 예외인 input이 너무 많았다. 방법을 달리 생각해 보니 A[i...i+1]을 선택하여 둘만 확인하는 것이 답의 최소인 조건이라고 생각하였고 해결할 수 있었다.

 

시간복잡도

O(n)

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
using namespace std;
 
void solution(vector<int>& V) {
    for(int i = 1; i < V.size(); i++) {
        if(abs(V[i] - V[i-1]) > 1) { //두 개 선택 시 Max,Min은 각각 둘 중 하나이므로
            cout << "YES" << endl;
            cout << i << " " << i+1 << endl;
            return;
        }
    }
    cout << "NO" << endl;
}
 
int main(void) {
    int test_cases;
    cin >> test_cases;
    for(int i = 0; i < test_cases; i++) {
        int n;
        cin >> n;
        vector<int> v(n);
        for(int j = 0; j < n; j++) {
            cin >> v[j];
        }
        solution(v);
    }
    
    return 0;
}

 

C. Make Good

문제 요약

임의의 정수 배열 A가 있다고 할 때, SUM(A) = 2 * XOR(A) 를 만족하는 A는 좋은 배열이라고 말한다. 앞의 식을 만족하기 위해 필요한 정수를 최대 3개 뽑고 이 정수들을 출력하는 문제이다.

 

접근 방법

처음엔 반복을 돌려야 하는건지 생각해 보았으나, 이 문제의 태그에 bitmasks가 달려 있는 것을 보고 단순 비트마스크 문제로 보는 것이 맞다고 생각했다. 정수 a에서 a XOR a = 0이므로, XOR의 특징을 통해 문제를 풀 수 있을 것 같았다.

 

시간복잡도

sum과 xor을 구하는 데 O(n)이 소요되고 값을 출력하는 데는 O(1)이므로 O(n)이 소요된다.

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
using namespace std;
 
void solution(vector<int>& V) {
    unsigned long long sum = 0, xr = 0;
    for(int i = 0; i < V.size(); i++) {
        sum = sum + (unsigned long long) V[i];
        xr = xr ^ V[i];
    }
    if(sum == 2 * xr) { //이미 식을 만족함
        printf("0\n\n");
    } else { //나머지
        printf("2\n");
        //sum + (xor) + (sum + xor) = 2 * (sum + xor) 이고,
        //xor ^ (xor) ^ (sum + xor) = sum + xor 이 되므로,
        //두 수 xor과 sum + xor을 더해주면 된다.
        printf("%llu %llu\n", xr, xr+sum);
    }
}
 
int main(void) {
    int test_cases;
    cin >> test_cases;
    for(int i = 0; i < test_cases; i++) {
        int n;
        cin >> n;
        vector<int> v(n);
        for(int j = 0; j < n; j++) {
            cin >> v[j];
        }
        solution(v);
    }
    
    return 0;
}

 

총평

처음 C번 문제를 풀었을 때는 좌변이 우변보다 작고 좌변이 짝수인 경우를 따로 놓고 풀었는데, 다 풀고 보니 좌변이 더 작은 경우를 체크하지 않아도 문제가 해결되었다.

D번 문제는 Interactive problem이라서 문제에 손을 대지 못했다. 다른 사람은 어떻게 풀었는지 읽어 보고 풀어봐야지.

2020년이 끝날 즈음이면 한 E번 문제정도 까진 풀 수 있는 능력이 되었으면 좋겠다.