Codeforces Round #763 (Div. 2) A부터 C까지 업솔빙

Codeforces Round #763 (Div. 2) A부터 C까지 업솔빙

B번 문제를 이해 못해서 엄청 낮은 퍼포를 받았다. 심지어 A번 문제 해답을 생각하기까지 40분이라는 시간이 걸린걸 보면 나는 알고리즘에 재능이 없는게 아닐까? 너무 실력이 들쑥날쑥 한것 같다. 폭풍성장을 희망하면서 해설 시작해보자.

A. Robot Cleaner (*800)

접기/펼치기

문제 설명
로봇 청소기가 사방이 벽으로 둘러싸인 직사각형 방 바닥에 놓여있다. 바닥은 길이가 $n$인 행과 $m$인 열로 이루어져 있다. 바닥의 행은 맨 위에서 1부터 $n$까지 번호가 있고, 열은 왼쪽부터 오른쪽으로 $1$부터 $m$까지 번호가 매겨져 있다. 로봇 청소기의 초기 위치는 $(r_b, c_b)$이다.

1초에 로봇 청소기는 행 $dr$, 열 $dc$만큼 이동한다. 1초가 지나면 로봇은 $(r, c)$에서 $(r + dr, c + dc)$ 만큼 이동한다. 처음에는 $dr = 1, dc = 1$ 이다. 만약 수평인 벽을 만난다면 $dc$는 $-dc$가 된다. 만약 수직인 벽을 만난다면 $dr$은 $-dr$이 된다.

각 초마다(로봇이 청소를 시작한 순간도 포함) 로봇은 같은 행 혹은 같은 열 모두를 청소한다.

크기가 $n \times m$인 바닥, 로봇의 초기 위치 $(r_b, c_b)$, 더러운 칸의 위치 $(r_d, c_d)$가 주어졌을 때, 더러운 칸을 청소하기 위해서 필요한 시간을 구하라.

문제 해설
처음에 그냥 단순한 구현 문제인줄 알았는데, 내가 구현한 방법이 틀려서 계속 시간 초과를 받았었다. 그래서 고민을 계속 한 결과 문제에 있는 반사라는 단어에서 영감을 얻었고, 이 방법이 쉽게 푸는 정해였다.

로봇이 벽을 부딪혔을때 로봇이 반사가 된다고 생각하지말고 공간이 하나 더 생겨서 통과한다고 생각해보자. 로봇은 처음에 $dr = 1, dc = 1$이기 때문에 계속 좌표가 더해진다. 만약 초기 로봇 위치보다 더러운 칸의 위치가 더 크다면 그냥 더러운 칸에서 초기 로봇 위치까지 변위를 구하면 되고, 행, 열의 변위를 각각 구한다음에 최솟값을 구하면 된다.

문제는 초기 로봇 위치보다 더러운 칸의 위치가 작은 경우이다. 이 경우에는 필연적으로 로봇이 반사할 수 밖에 없는데, 이때 공간이 하나 더 생긴다는 생각을 해보자. 로봇이 이동하다가 벽을 만나면 똑같은 크기를 만나는 벽에 그린다음에 정확히 대칭이 되게 그린다면 더러운 칸의 위치가 초기 로봇 위치보다 커지게 되고 변위를 쉽게 구할 수 있게 된다. 정확한 값은 코드를 참고하면서 이해해 보자. 간단한 거울 문제이다. 주의해야 할것은 행과 열을 따로 고려해서 최솟값을 구해야 하는 점이다.

정답 코드

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

using pii = pair<int, int>;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n, m, rb, cb, rd, cd; cin >> n >> m >> rb >> cb >> rd >> cd;
        if(rb > rd) rd = 2 * n - rd;
        if(cb > cd) cd = 2 * m - cd;
        cout << min(rd - rb, cd - cb) << "\n";
    }
    return 0;
}

B. Game on Ranges (*1100)

접기/펼치기

문제 설명
앨리스와 밥은 이어서 설명할 게임을 진행중이다. 앨리스는 처음에 오직 $1$개 범위 $[1, n]$이 들어있는 집합 $S$를 가지고 있다. 앨리스는 집합 $S$에서 범위 $[l, r]$을 선택하고 선택한 범위 안에서 밥이 선택한 숫자는 무엇인지 물어본다. 밥은 숫자 $d (l \le d \le r)$을 선택한다. 그리고 앨리스는 $S$에서 $[l, r]$을 제거하고 $S$에 범위 $[l, d - 1] (l \le d -1)$, 범위 $[d + 1, r] (d + 1 \le r)$를 넣는다. $S$가 빌때까지 게임은 진행한다. 이 게임은 반드시 $n$번만 수행한다.

게임이 끝나고 나서 앨리스는 $S$에서 선택한 범위 $[l, r]$을 기억한다. 하지만 밥은 자신이 선택한 숫자를 기억 못한다.

앨리스가 선택한 범위 $[l, r]$ 의 배열이 주어질때, 밥이 선택한 숫자 $d$를 구하라.

문제 해설
처음 이 문제를 봤을 때 이해가 안되서 결국 업솔빙한 문제이다. 해설을 보고 나니 문제를 바로 이해해 버려서 조금 허탈한 문제였다. 일단 $1$부터 $n$까지 숫자가 반드시 한번만 나와야 한다. 왜냐하면 숫자 $d$를 선택했을때, $d$를 제외한 범위를 넣었기 때문에 이 이후에는 $d$를 선택할 수 없기 때문이고, 이 게임은 반드시 $n$번만 수행된다는 조건 때문이다.

가장 먼저 알 수 있는 점은 $[l, r]$에서 $l = r$이면 밥은 반드시 $l$을 선택해야 한다는 것이다. 그러면 $r - l$의 차이가 작은 순으로 그리디하게 판단하면 풀 수 있을 것이다. 이 게임을 끝내기 위해서 반드시 $l = r$인 구간이 나올 것이고 그걸 시작으로 한번 선택한 수는 다시 선택할 수 없다는 규칙 때문에 이 문제를 그리디 하게 풀 수 있다.

처음에 원소가 $n$개인 배열을 선언한다. 이 배열은 밥이 $d$를 선택했는지 표시하는 배열이다. 만약 범위를 골랐는데, 위의 배열에 선언하지 않은 값이 있으면 그 값을 출력하고 선택했다고 표시한다. 즉 먼저 $d$의 존재여부 배열을 만들고 구간을 차이가 작은 순으로 정렬한 다음 맨 처음 값부터 차례로 확인한다면 문제를 풀 수 있다. 이때 주의해야할 것은 $d$는 $l \le d \le r$이라는 점이다. 이 성질 때문에 그리디하게 문제를 풀 수 있다.

정답 코드

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

using pii = pair<int, int>;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        vector<pii> v;
        vector<int> cnt(n + 1);
        for(int i = 0; i < n; i++){
            int a, b; cin >> a >> b;
            v.push_back({a, b});
        }

        sort(v.begin(), v.end(), [](pii& a, pii& b){
            return a.second - a.first < b.second - b.first;
        });

        for(auto x : v){
            cout << x.first << " " << x.second << " ";
            for(int i = x.first; i <= x.second; i++){
                if(!cnt[i]){
                    cout << i << "\n";
                    cnt[i] = 1;
                    break;
                }
            }
        }
        cout << "\n";
    }
    return 0;
}

C. Wrong Addition (*1600)

접기/펼치기

문제 설명
돌꾸러미 $n$개가 주어진다. $i$번째 꾸러미에는 돌 $h_i$개가 있다. 돌 꾸러미 안에 있는 돌의 개수를 다음과 같은 과정을 거쳐서 바꾸고 싶다.

• $3$번째 꾸러미에서 부터 $n$번째 꾸러미 순서대로 진행한다.
• $i$를 현재 꾸러미라고 가정하자.
• $(0 \le 3 \cdot d \le h_i)$인 $d$를 선택한다. 돌 $d$개를 $i$번째 꾸러미에서 꺼내 $i - 1$번째 꾸러미에 주고, 돌 $2d$개를 $i$번째 꾸러미에서 꺼내 $i - 2$번째 꾸러미에 준다.
• 그러면 $h_i$는 $3d$만큼 감소하고, $h_{i - 1}$은 $d$만큼 증가하며 $h_{i - 2}$는 $2d$만큼 증가한다.
• 각 다른 연산마다 같거나 다른 $d$를 선택할 수 있고, 몇개 꾸러미는 비어있을 수 있다. 이때는 여전히 꾸러미로 취급한다.

과정을 모두 완료한 이후에 가장 작은 꾸러미에 있는 최대 돌의 개수를 구하라.

문제 해설
문제를 처음 보고나서 이건 무조건 이분 탐색 문제라고 생각했지만 어떻게 푸는지 모르겠다. 아직 경험이 부족하다는 생각이 계속든다. 도대체 얼마나 풀어야 이 문제를 쉽게 풀 수 있을까?

문제에서는 가장 작은 꾸러미에 있는 돌의 개수를 $x$라고 두고, 이 값을 이분탐색을 이용해 찾았다. 그러면 일단 $x$의 최소값은 $0$이고, 최대값은 배열의 최대값 + 1이다. 그래서 이 범위를 기준으로 이분 탐색을 해서 $x \le a[i]$를 만족하는 최대 $x$를 구해야 한다는 이분 탐색 문제로 바뀐다. 이때 $a[i]$는 모든 과정을 마친 후 $i$번째 꾸러미에 있는 돌 개수이다.

일단 $x$가 $0$이면 무조건 답이다. 왜냐하면 $3d$는 반드시 $h_i$보다 작기 때문에 돌을 아무리 꾸러미에서 꺼내도 $0$보다 작아지지 않기 때문이다. 그리고 $x$가 최대값 + 1이면 반드시 답이 안된다. 그러면 $TTTTTTFFFFFF$인 문제를 푸는 이분탐색 문제가 되고, T에서 F로 바뀌는 그 구간을 찾아서 $lo$값을 출력하면 최대 $x$값이 된다.

그러면 이제 결정 함수만 만들면 이 문제를 해결한다. $x$는 가장 작은 꾸러미에 있는 돌의 개수이고 $x \le a[i]$를 만족하는 최대 $x$를 구해야 한다. 그런데 이 연산을 순서대로 $3$번째 꾸러미에서 $n$번째 꾸러미로 계산하면 값이 계속 변동하기 때문에 파악하기 힘들다. 그렇기 때문에 연산을 반대로 수행해보자. $n$번째에서 시작해서 $3$번째 꾸러미로 이동하자. 그러면 $3d = h_i - x$가 된다. 이때 $0 \le 3d$이기 때문에 $x > h_i$이면 조건을 만족하는 $d$가 없기 때문에 바로 false라고 판단한다.

그러면 단순히 $d$를 찾고 $i-1$번째에 $d$를 더하고, $i - 2$번째에 $2d$를 더하면 될까? 이때 $i$번째 꾸러미는 볼 필요 없다. 왜냐하면 $d$가 구해진 순간에 이미 $x \le h_i$이기 때문이다. 문제는 앞에서 부터 연산하는데 우리는 뒤에서 부터 연산하기 때문에 말이 안되는 $d$값이 나울 수도 있다. 그리고 이 경우를 처리해줘야 한다. $3d \le h_i$이기 때문에 기존 $h_i$값을 넘어선 $3d$값이 나올 경우 그냥 기존 $h_i$를 골라서 처리해야한다. 그렇기 때문에 $min(a[i], cur[i] - x)$ 코드가 나온 것이다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int a[n];
        for(auto& x : a) cin >> x;
        int lo = -1, hi = *max_element(a, a + n) + 1;
        auto check = [&](int x){
            vector<int> cur(a, a + n);
            for(int i = n - 1; i > 1; i--){
                if(cur[i] < x) return false;
                int d = min(a[i], cur[i] - x) / 3;
                cur[i - 1] += d;
                cur[i - 2] += 2 * d;
            }
            return cur[0] >= x and cur[1] >= x;
        };

        while(lo + 1 < hi){
            int mid = (lo + hi) / 2;
            if(check(mid)) lo = mid;
            else hi = mid;
        }
        cout << lo << "\n";
    }
    return 0;
}