[Codeforces] Codeforces Round 988 (Div. 3) 후기

최근 백준 닉네임에 색을 칠하고 싶어 Codeforces를 시작하게 되었다.

시작한지 얼마 되지 않아서 Div. 2에서 벽을 많이 느꼈었는데, 이번 Div. 3에서 자신감을 되찾고자 참가하게 되었다.

그리고 이번 Div. 3에서 Rating을 103점 이상 얻으면 Pupil 을 갈 수 있기 때문에 기대를 가지고 참가했다.

Contest 링크 : Codeforces Round 988 (Div. 3)

A. Twice

길이가 $n$인 정수 배열 $a$가 주어진다.

주어진 입력에서 $1 \leq i < j \leq n$인 $i, j$에 대해 $a_i = a_j$를 만족하는 개수를 찾는 문제였다.

모든 입력을 map<int, int>에 넣고 map을 모두 순회하면서 2로 나눈 값을 cnt변수에 모두 더해주었다.

코드 보기

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        map<int, int> m;
        for (int i = 0; i < n; i++) {
            int a; cin >> a;
            m[a]++;
        }

        int cnt = 0;
        for (auto i : m) cnt += i.second / 2;
        cout << cnt << '\n';
    }
}

B. Intercepted Inputs

길이가 $k$인 정수 배열 $a_k$가 주어진다.

정수 배열에는 $n, m$과 $n * m$ 만큼의 원소가 포함되어 있는데 값들의 순서가 무작위로 섞여 한 줄로 주어진다.

그래서 원래 배열을 복원하기 위해 $n, m$을 찾는 문제이다.

임의의 $a_i, a_j$를 골라서 $a_i * a_j = k - 2$를 만족하는지 확인하면 된다.

A번과 마찬가지로 입력을 전부 map<int, int>에 저장하고 반복문을 $1$부터 $k - 2$까지 반복했다.

$k - 2$에 나누어 떨어지는 $i$를 대상으로 map에 $i$와 $(k - 2) / i$가 모두 존재하면 $n, m$을 찾았으므로 이를 출력하고 반복문을 종료하면 된다.

코드 보기

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        int k; cin >> k;
        map<int, int> m;
        for (int i = 0; i < k; i++) {
            int a; cin >> a;
            m[a]++;
        }

        for (int i = 1; i <= k - 2; i++) {
            if ((k - 2) % i) continue;
            if (m.find(i) != m.end() && m.find((k - 2) / i) != m.end()) {
                if (i == (k - 2) / i && m[i] < 2) continue;
                cout << i << ' ' << (k - 2) / i << '\n';
                break;
            }
        }
    }
}

C. Superultra’s Favorite Permutation

$n$이 주어진다.

주어진 입력에서 모든 $1 \leq i \leq n - 1$ 에 대해 $p_i + p_{i + 1}$는 합성수를 만족해야하고 $p$가 순열이 되도록 값을 구성해야 한다.

이때 불가능 하면 -1을 출력하고 가능하면 $p$를 출력하면 된다.

$n$이 1일 때부터 가능한 경우를 구성해 보았는데 $n$이 5일 때부터 아래와 같이 조건에 맞는 순열이 만들어지는 것을 알 수 있었다.
$$[1, 3, 5, 4, 2]$$

5 이상일 때 어떻게 순열을 구성해야 하는지 고민을 좀 오래 했는데 홀수끼리 더하면 항상 짝수가 나오고 짝수끼리 더하면 항상 짝수가 나오기 때문에 이 성질을 이용하면 될 것이라 생각했다.

왼쪽에는 홀수만 몰아넣고, 오른쪽에는 짝수만 몰아 넣은 다음 홀수와 짝수가 만나는 부분엔 더했을 때 소수가 나오지 않는 수를 붙여 놓으면 된다.

이때 홀수와 짝수가 만나는 부분엔 5와 4를 배치하면 $p_i + p_{i + 1}$는 합성수를 항상 만족할 수 있다.

코드 보기

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        int n; cin >> n;

        if (n < 5) cout << "-1\n";
        else {
            for (int i = 1; i <= n; i += 2) {
                if (i == 5) continue;
                cout << i << ' ';
            }
            cout << 5 << ' ' << 4 << ' ';
            for (int i = 2; i <= n; i += 2) {
                if (i == 4) continue;
                cout << i << ' ';
            }
            cout << '\n';
        }
    }
}

D. Sharky Surfing

$n, m, L$이 주어진다.

$n$은 장애물의 개수, $m$은 파워업 아이템의 개수, $L$은 도착 할 지점이다.

이후 $n$개의 장애물이 존재하는 구간 $[l, r]$과 $m$개의 파워업의 (위치 $x_i$, 크기 $v_i$)가 주어진다.

점프력이 $k$이고 현재 위치가 $x$일 때 구간 $[x, x + k]$ 사이 위치로 원하는 만큼 이동할 수 있고 이동하려는 위치에 장애물이 존재하면 해당 위치로 이동할 수 없다.

파워업 아이템을 먹으면 점프력이 $v_i$만큼 증가한다.

시작 위치가 1, 점프력이 1일 때 $L$에 도착하기 위해 필요한 파워업 아이템의 최소 개수를 구해야 한다.

장애물을 한 개씩 모두 지나가면서 장애물을 건널 수 없으면 장애물을 건널 수 있을 때까지 파워업 아이템을 먹으면 된다.

이때 파워업 아이템을 먹는 개수를 최소화해야 하기 때문에 priority_queue<int>를 사용해 점프력이 많이 증가하는 아이템부터 먹었다.

연속한 두 장애물 사이에 존재하는 파워업 아이템을 upper_bound를 이용해 모두 priority_queue에 넣어놓고 장애물을 건널 수 없으면 건널 수 있을 때까지 먹어주었다.

priority_queue가 비어있다면 다 먹었어도 건널 수 없는 경우이기 때문에 -1을 출력해주고 그렇지 않다면 계속해서 전진했다.

코드 보기

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        int n, m, L; cin >> n >> m >> L;
        vector<pair<int, int>> v1(n), v2(m);
        // 장애물
        for (auto& [l, r] : v1) cin >> l >> r;

        // 파워업
        for (auto& [x, v] : v2) cin >> x >> v;

        // 파워업 후보
        priority_queue<int> pq;
        int sum = 1, cnt = 0;
        int p1 = 0, p2 = 0, cur = 0;
        while (cur < L) {
            int p = upper_bound(v2.begin(), v2.end(), v1[p1]) - v2.begin();
            for (int i = p2; i < p; i++) pq.push(v2[i].second);
            while (v1[p1].second - v1[p1].first + 2 > sum) {
                if (pq.empty()) {
                    cnt = -1;
                    break;
                }
                sum += pq.top();
                cnt++;
                pq.pop();
            }
            if (cnt == -1) break;
            p1++;
            p2 = p;
            if (p1 == n) break;
            cur = v1[p1].first - 1;
        }
        cout << cnt << '\n';
    }
}

 

구현을 제대로 한 것 같지 않고, 시간 복잡도도 확신이 들지 않아 WA나 TLE를 예상했었는데 의외로 한번에 Accepted가 나와서 놀랐다.

E. Kachina’s Favorite Binary String

인터렉티브 문제이다.

어떤 이진 문자열에 대해 길이 $n$이 주어진다.

우리가 “? a b”라고 질의하면 $[a, b]$ 내에 존재하는 “01”형태의 서브 시퀀스의 개수를 알려준다.

예를 들어 문자열이 “0010”일 때 “? 1 4”라고 질의 하면 서브 시퀀스는 $(a_1(0), a_3(1))$과 $(a_2(0), a_3(1))$ 두 개 존재하므로 2라고 답변한다.

길이 $n$의 문자열에 대해 질의를 최대 $n$번 할 수 있을 때 문자열을 확인할 수 있으면 정답 문자열 s에 대해 “! s”를 출력하고 확인할 수 없다면 “! IMPOSSIBLE”을 출력해야 한다.

D번까지는 풀이법이 바로 바로 생각나서 어렵지 않게 풀 수 있었는데 해당 문제는 풀이법 조차 생각나지 않았다.

힘들게 고민하다가 옳은 풀이인지는 모르겠고 아무 방법이나 사용해보자 해서 앞에서 부터 3개씩 확인해보기로 했다.

숫자 3개에 대해 나올 수 있는 조합과 01 서브 시퀀스의 개수는 아래와 같다.
$$ 000(0), 001(2), 010(1), 011(2), 100(0), 101(1), 110(0), 111(1) $$

결과가 1이면 010, 101 중 하나이므로 구간의 길이를 2로 줄여서 다시 질의하면 알 수 있고

2일 때도 001, 011이므로 구간의 길이를 2로 줄이면 된다.

0일 때는 알 수 없으므로 한칸 뒤로 가서 다시 질의하는 방식으로 구현했다.

당연히 모두 WA가 나왔다.

결국 풀지 못하고 Contest가 종료되었다.

F. Ardent Flames , G. Natlan Exploring

E번을 푸느라 두 문제 모두 풀지 못했다.

후기

푼 문제들은 다 한 번에 Accepted를 받은 것이 좀 의외였다.

E번을 풀 수 있었으면 좋았을텐데 Contest가 끝나고 풀이를 봤을 때 전혀 생각하지 못한 방법이었어서 아쉬움은 덜했다.

C번 풀 때 홀수 / 짝수 모으기를 생각 안한 상태에서 일정 개수 넘어가면 뒤에 덧붙이면 되지 않을 까란 생각에 하드 코딩하다가 $n =8$에서 갑자기 순열이 확 바뀌다보니까 하드 코딩을 멈추고 규칙성을 찾기 시작했는데 정말 잘한 것 같다.

무사히 Pupil 을 갈 수 있었다