Educational Codeforces Round 117 A부터 D까지 업솔빙

Educational Codeforces Round 117 A부터 D까지 업솔빙

C번 문제하고 D번 문제가 개인적으로 정말 좋았다고 생각하는 대회이다. C번문제는 이분탐색밖에 모르던 내가 파라메트릭 서치를 알게해줬고, D번 문제는 알고리즘을 공부하려고 정수론을 공부하는 것은 정말 어리석은 짓이라는 것을 깨닫게 해줬다. 이번 대회는 상대적으로 수학이 많이 나왔는데, 수학 문제 특성상 그리디처럼 문제를 온몸 비틀어서 푸는게 아니라 규칙만 딱 찾으면 답이 나와서 기존 대회보다는 답을 구하는 과정만 이해하면 나머지 코딩은 쉬웠다.
이번 대회에서 배운 것은

1. 이분탐색과 파라매트릭 서치
2. 나머지 연산과 나눗셈 연산과 뺄셈
3. 좌표평면이 나오면 꼭 그려서 해보기

A. Distance (*800)

접기/펼치기

문제 설명
두 점 $p_1 (x_1, y_1)$과 $p_2 (x_2, y_2)$ 사이의 맨해튼 거리를 $d(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2|$ 라고 정의하자.

두 점 $A, B$가 주어지고 점 $A$의 좌표는 $(0, 0)$ 이고, $B$의 좌표는 $(x, y)$ 이다.

우리의 목표는 다음 조건을 만족하는 점 $C$를 찾는 것이다.

• $C$의 두 좌표는 모두 음이 아닌 정수이다.
• $d(A, C) = \frac{d(A, B)}{2}$ 반올림은 없다.
• $d(B, C) = \frac{d(A, B)}{2}$ 반올림은 없다.

문제 해설
$x, y$값이 모두 양수라고 문제에서 주어졌기 때문에 $x + y$를 해서 값이 줄어든다하는 불상사가 일어나지 않는다. $d(A, B)$는 결국 $|x + y| = x + y$랑 같기 때문에 이 수가 홀수면 위의 두 등식을 만족하는 점 $C$는 없다.

$x + y$가 짝수라면 맨해튼 거리를 어떻게 정의하는지 생각해보자.

결국 맨해튼 거리는 두 거리를 직각모양으로 정의하는데, 그러면 제일 쉽게 $C$를 찾는 방법은 점이 맨해튼 거리상에 위치해야 한다는 것이다. 점 C가 맨해튼 거리의 정확히 절반이 되기 위해서는 어떻게 해야할까?

맨해튼 거리의 절반을 구한다음, $x, y$중 더 큰 수의 좌표값에서 거리의 절반을 빼고, 남은 좌표는 그대로 두면 된다.

잘 이해가 안되는 사람은 내가 답을 구한과정을 그림으로 그려보면 더 쉽게 이해할 수 있다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int x, y; cin >> x >> y;
        int sum = x + y;
        if(sum & 1) cout << -1 << " " << -1;
        else{
            if(x < y) cout << x << " " <<  y - sum / 2;
            else cout << x - sum / 2 << " " << y;
        }
        cout << "\n";
    }
    return 0;
}

B. Special Permutation (*1000)

접기/펼치기

문제 설명
길이가 $n$인 순열이 배열 $p = [p_1, p_2, ..., p_n]$ 에 있다.

$n$은 짝수인 세 숫자 $n, a, b$ 가 주어진다. 배열 $p$의 왼쪽 절반에 있는 원소들 중에서 $a$가 가장 작은 원소가 되고, 배열 $p$의 오른쪽 절반에 있는 원소들 중에서 $b$가 가장 큰 원소가 되는 배열 $p$를 출력하라. 만약 그러한 배열이 없다면 $-1$을 출력한다.

문제 해설
가장 먼저 확인할 수 있는 사실은 왼쪽 절반에 있는 원소들 중에서 $a$가 가장 작은 원소가 되려면 오른쪽 절반에 $a$보다 작은 원소들 전부를 넣어야 한다. 그리고 오른쪽 절반에 있는 원소들 중에서 $b$가 가장 큰 원소가 되려면 왼쪽 절반에 $b$보다 큰 원소들 전부를 넣어야 한다.

$a$보다 작은 원소의 개수는 $a - 1$이며, $b$보다 큰 원소의 개수는 $n - b$ 이다. 그리고 이 개수가 $n / 2$를 초과하면 $a$보다 작은 원소, $b$보다 큰 원소가 옆으로 흘러넘치기 때문에 답이 될수가 없다.
$a - 1 = n / 2, n - b = n / 2$ 이면 어떨까? 이 경우는 정확히 절반이 되기때문에 답이 될 수 있다.

그렇다면 위의 조건을 통과했을 때 수열을 어떻게 만들어야할까? 나는 대회중에서 규칙을 찾아서 겨우 만들었지만 문제 정해는 다음과 같다. $a$를 맨 앞에, $b$를 맨뒤에 넣은 다음, $a$와 $b$가 아닌 나머지 원소를 내림차순으로 쭉 넣으면 구할 수 있다. $a$가 왼쪽 절반에 가장 작은 원소여야 하기 때문에 제일 큰 수 부터 차례대로 넣으면 된다. 마찬가지로 $b$가 오른쪽 잘반에 가장 큰 원소여야 하기 때문에 왼쪽 부터 제일 큰 수 부터 차례대로 넣으면 결국 오른쪽 절반에는 왼쪽 보다 작은 원소들이 들어갈 것이다.

정답 코드

#include <iostream>
#include <algorithm>
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, a, b; cin >> n >> a >> b;
        if((n / 2 < b && a < n / 2 + 1) || (b == n / 2 && a == n / 2 + 1)){
            cout << a << " ";
            for(int i = n; i > 0; i--){
                if(i != a && i != b) cout << i << " ";
            }
            cout << b << "\n";
        }else cout << -1 << "\n";
    }
    return 0;
}

C. Chat Ban (*1300)

접기/펼치기

문제 설명
당신은 온라인 스트리밍 플랫폼에서 채팅을 치고 있는 유저이다.

정확히 당신은 크기가 $k$인 삼각형으로 이모티콘을 치고 싶다. 이 삼각형은 총 $2k - 1$개 문자로 이루어져 있다. 첫번째 메시지는 $1$개 이모티콘, 두번째 메시지는 $2$개 이모티콘..., $k$번째 메시지는 $k$개 이모티콘, $k + 1$번째 메시지는 $k - 1$개 이모티콘, ... 마지막 메시지는 $1$개 이모티콘으로 이루어져 있다.

예를 들어서 $k = 3$인 삼각형은 총 $5$개 메시지로 이루어져 있다.

물론 대부분 체널은 자동 체팅 벤 기능이 있다. 이 기능은 연속해서 최소 $x$개 이모티콘을을 입력하면 자동으로 벤이 된다. 우리의 목표는 벤이 되기 전에 얼마나 많은 메시지를 칠 수 있는지 찾는 것이다. 혹은 벤이 되지 않을 수도 있다. ($2k - 1$ 개 메시지를 쓰고 삼각형을 완전히 만들 수도 있다는 뜻이다.) 만약 메시지를 쓰고난 후 벤이 되었다면 그 메시지는 개수에 포함된다.

문제 해설
$1$ 부터 $n$까지 덧셈을 하면 등차수열의 합 공식에 의해서 $cnt(n) = \frac{n(n + 1)}{2}$ 이다.
이 문제는 이분탐색의 변형인 파라매트릭 서치 알고리즘을 사용하는 전형적인 문제다. 만약 우리가 $y$번째 메시지까지를 작성하고 벤이 되었다면 $cnt(y) \ge x$를 만족한다는 뜻인데, 이 조건을 만족하는 $y$를 찾으려면 일단 범위가 $10^9$ 까지라서 $O(n)$으로 찾는다면 무조건 시간초과가 난다.

그렇기 때문에 $cnt(y) >= x$ 이 조건을 만족하는 $y$를 이분탐색으로 찾아야 하는 것이다. 조건에 맞는 값을 이분 탐색으로 찾는 알고리즘을 우리는 파라매트릭 서치라고 하고 하는 방식은 이분 탐색과 비슷하다. 그러면 $cnt(y)$는 어떻게 구성할까? 삼각형이 $k$를 중심으로 변화 양상이 다르기 때문에 $y = k$를 기준으로 범위를 나눠보자.

• $y < k$인 경우, 단순히 $\frac{y(y + 1)}{2}$ 로 구간합을 구한다.
• $y \ge k$ 인 경우, 일단 $k$번째까지 메시지를 작성했고 그 값은 $cnt(k)$이다. 그 다음 추가로 $y - k$개 메시지를 더 작성했다. 그 나머지 메시지는 $1$ 부터 $k - 1$개 메시지의 합에서 $1$ 부터 $2k - 1 - y$번째 메시지까지 합을 빼면 구할 수 있다. 즉 $cnt(k) + cnt(k - 1) - cnt(2k - 1 - y)$로 구할 수 있다.

만약 찾은 $y$에 대한 합계 $sum \ge x$ 식을 만족한다면 ans에 그 y를 추가하고 범위를 왼쪽 절반으로 해서 최소 $y$값을 찾는 여정을 시작한다. 왜냐면 만약 $5$번째 메시지를 치자마자 벤이 됬는데, 그러면 그 이후로 치는 모든 메시지는 모두 벤이 된다. 따라서 현재 찾은 값이 벤이 되기 전까지 무조건 칠 수 있는 최대 메시지 값이라는 보장이 없기 때문이다.
만약 $sum < x$ 라면 아직 메시지를 더 칠 수 있기 때문에 범위를 오른쪽 절반으로 해서 저 식을 만족하는 $y$를 찾는 여정을 시작한다.

주의할 점은 저 식을 만족하지 못하면 모든 메시지를 다 작성할 수 있다는 뜻이고, $2k - 1$을 출력해야 한다.

정답 코드

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

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        ll k, x; cin >> k >> x;
        ll l = 1, r = 2 * k - 1;
        ll ans = r;
        while(l <= r){
            ll mid = (l + r) / 2;
            ll sum = 0;
            if(mid < k) sum = mid * (mid + 1) / 2;
            else{
                ll idx = 2 * k - 1 - mid;
                sum = k * k - idx * (idx + 1) / 2;
            }

            if(sum >= x) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        cout << ans << "\n";
    }
    return 0;
}

D. X-Magic Pair (*1600)

접기/펼치기

문제 설명
정수 한 쌍 $(a, b)$와 정수 $x$가 주어진다.

이 쌍을 두가지 다른 방식으로 바꿀 수 있다.

• $a = |a - b|$
• $b = |a - b|$

만약 주어진 연산을 해서 $(a, b)$ 중 아무나 $x$를 얻을 수 있다면 $(a, b)$는 $x-magic$ 이라고 한다. 즉 연산을 여러번 적용했을 때, $a = x$ 혹은 $b = x$이라면 $x-magic$이다.

주어진 쌍 $(a, b)$가 $x-magic$인지 아닌지 판별해야 한다.

문제 해설
느그 정수론 문제~~, 생각보다 아이디어는 어렵지 않아서 이해하는데 오래 걸리지 않았다. 일단 주어진 쌍을 몇번 만져보면 $a, b$중 큰 수에 연산을 적용해야 하는 것을 알 수 있다. 작은수에 적용하면 언젠가는 다시 원래 상태로 돌아오기도 하고, 똑같은 연산을 중복해서 한다는 사실을 알 수 있다.

그러면 단순히 연산과정을 반복해서 $x$가 나올때 까지 하면 되는가? 그것도 아니다. 주어진 숫자 제한이 $10^{18}$ 이기 때문에 무조건 TLE가 난다. 그래서 최적화가 필요하다.

초등학교때 배운적이 있을 것이다. 곱셈은 덧셈의 연속이고, 나눗셈은 뺄셈의 연속이다. 그러면 한 수를 여러번 빼고 나서 남은 수는 어떻게 구할까? 나머지 연산을 이용하면 된다!

현재 쌍이 $(a, b)$이고, $x$가 주어지고 $a$는 항상 큰 수라고 가정을 일단 하자. 그러면 $a$값이 바뀔텐데, $a$에서 $b$를 최대한 빼는 과정에서 $x$가 나올수 있는지 확인을 해야한다. 그러면 $a - x$ 숫자를 총 빼야 하는데, 이 값을 $b$로 나누었을 때 나누어 떨어진다면 $a$에서 $b$를 여러번 빼서 $x$를 구할 수 있다는 것이고, 나누어 떨어지지 않는다면 $x$를 구할수 없다는 뜻이 된다. 이런식으로 구하면 된다.

정답 코드

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

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        ll a, b, x; cin >> a >> b >> x;
        bool flag = false;
        while(a != 0 && b != 0){
            if(a < b) swap(a, b);
            if(a < x) break;
            if((a - x) % b == 0){
                flag = true;
                break;
            }
            a %= b;
        }

        cout << (flag ? "YES" : "NO") << "\n";
    }
    return 0;
}