Educational Codeforces Round 118 A부터 C까지 업솔빙

Educational Codeforces Round 118 A부터 C까지 업솔빙

A번에서 뇌절한 문제셋이다. 왜 뇌절했냐고? *900문제가 나와서... *800문제는 이제 쉽게 풀 수 있는데 *900문제는 쉽게 생각하면 안될 것 같다. 어찌 어찌 풀지만 시간이 너무 오래걸린다. 이런 문제를 제때제때 풀어야 실력이 는다고 생각을 하면서 풀어보자. 그리고 또나온 파라매트릭 서치. 안 푼지 며칠이나 지났다고 벌써 까먹었다. 이번에 풀어본 문제가 전형적인 파라매트릭 서치 문제라고 하니까 다시한번 눈도장을 찍어보자.
이번 대회에서 배운 것은

1. 파라매트릭 서치의 기본 문제, 유형
2. 조건 분기 침착하게 하기

A. Long Comparison (*900)

접기/펼치기

문제 설명
지수는 칠판에 두 숫자를 적었다. 두 숫자는 다음 특별한 형식을 따른다. 양의 정수 x의 뒤에 $0$ $p$개가 붙는다.

이 두 숫자중에서 누가 더 큰지 작은지 비교해야 한다.

문제 해설
두 수를 비교하는 것인데, $p \le 10^6$ 이므로 기본적인 long long 타입으로는 이 문제를 풀 수 없다. 띠라서 문자열로 풀어야한다는 생각이 가장 먼저 들었는데, 계속 문자열로 풀어도 오답이 나길래 B번 문제로 넘어갔다가 B번문제가 수학 문제여서 A번문제도 그냥 로그를 이용한 수학문제로 풀었다. 그런데 이것도 침착한 테스트 케이스 나누기로 풀 수 있다.

일단 두 수를 비교하기 위해서는 전제조건이 있다. 두 수의 자릿수가 같아야 한다는 점이다. 이 점을 무시하고 그냥 무작정 문자열로 바꾸고 비교를 하면 답이 틀릴 수 밖에 없다. 따라서 이 숫자의 자릿수를 알야야하고 $p$는 그 자체가 자릿수에 포함되고 x는 문자열로 일단 받은 다음에 size를 이용해서 자릿수를 구한다.

그 다음에 자릿수가 만약 다르다면 자릿수가 더 큰 수가 무조건 크다. 그렇지 않으면 자릿수가 같은 두 수를 비교해야하는데, 그냥 $p$만큼 $0$을 붙여서 string compare을 한다면 시간 복잡도가 $O(n)$ 이기 때문에 시간초과이다. 따라서 불필요한 $0$을 붙이는 행위를 제거해야하고 $p_1, p_2$중 작은 수 만큼 $0$을 제거해도 비교를 하는데 아무 상관이 없기 때문에 이 방법을 사용한다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        string x1, x2;
        int p1, p2;
        cin >> x1 >> p1 >> x2 >> p2;
        int len1 = x1.size() + p1;
        int len2 = x2.size() + p2;
        if(len1 > len2) cout << ">";
        else if(len1 < len2) cout << "<";
        else{
            int sub = min(p1, p2);
            p1 -= sub;
            p2 -= sub;
            string a = x1 + string(p1, '0');
            string b = x2 + string(p2, '0');
            cout << (a > b ? ">" : (a < b ? "<" : "="));
        }
        cout << "\n";
    }
    return 0;
}

B. Absent Remainder (*1000)

접기/펼치기

문제 설명
$n$개의 서로 다른 $n$개의 양수로 이루어진 수열 $a_1, a_2, ..., a_n$이 주어진다. 다음 조건을 만족하는 $x$와 $y$의 쌍 $[\frac{n}{2}]$ 개를 구하라.

• $x \neq y$
• $x$와 $y$는 $a$의 원소이다.
• $x \, mod \, y $는 $a$의 원소가 아니다.

$x$와 $y$는 수 많은 쌍에 들어갈 수 있다.

문제 해설
개인적으로는 $A$번 보다 쉬운 문제였다. $a$에서 가장 작은 원소를 $mi$라고 하면 $mi$를 제외한 모든 수를 $mi$로 나누면 나오는 나머지는 나머지 정리에 의해 $mi$보다 작기 때문에 무조건 $a$의 원소가 아니다. 왜냐하면 $a$의 가장 작은 원소가 $mi$이기 때문에 이보다 작은 원소는 $a$에 존재할 수 없기 때문이다. 따라서 $mi$를 제외한 남은 $a$의 원소와 $mi$를 $[\frac{n}{2}]$ 개 출력하면 된다.

정답 코드

#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; cin >> n;
        int a[n];
        for(auto& x : a) cin >> x;
        sort(a, a + n);
        for(int i = 1; i <= n / 2; i++) cout << a[i] << " " << a[0] << "\n";
    }
    return 0;
}

C. Poisoned Dagger (*1200)

접기/펼치기

문제 설명
지수는 아직도 컴퓨터 게임을 하고 있다. 지수의 캐릭터는 용을 죽여야 한다. 지수는 용을 독이 묻은 칼로 죽여야 한다. $i$번째 공격은 전투가 시작되고 나서 $a_i$초에 시작한다. 칼은 그 자체로 데미지가 없지만 용에게 중독 효과를 부여한다. 다음 $k$초 동안 $1$ 데미지를 준다. 단 만약 용이 이미 중독상태라면 단검은 중독 효과를 다시 처음부터 적용한다.(현재 중독 효과를 제거하고 새로운 중독 효과로 갱신)

용의 전체 체력이 $h$일때, 그리고 용에게 최소 $h$ 데미지를 주면 용을 죽일 수 있다. 지수가 용을 죽일 수 있는 최소 $k$를 구하라.

문제 해설
뻔하디 뻔한 문제지만 풀지 못한 문제.

이 문제가 바로 파라매트릭 서치의 전형적인 문제이다. $sum(x) \ge h$를 만족하는 최소 $x$를 구하는 문제가 바로 파라매트릭 서치가 사용되는 문제이기 때문이다. 일단 $h \le 10^{!8}$ 이기 때문에 $1$부터 $10^{18}$까지가 x의 후보이다. 이 후보중에서 $x$가 정해질때 $sum(x)$를 구해야 한다. $sum(x)$는 어떻게 구할까?

$a_i$는 오름차순으로 주어지기 때문에 우리가 알야할 것은 $a_{i + 1}$과 $a_i$차이값이다. 일단 $a_i$가 오름차순이기 때문에 앞에서 두 수의 차이가 $a$라면 뒤에서 나오는 수의 차이는 반드시 $a$보다 크다. 이 사실을 가지고 다음을 확인해보자. 만약 $k = 4$일 때, 차이값이 $3$이면 독의 효과는 그대로 $3$만큼 지속될 것이다. 만약 차이값이 $5$이라면 독의 효과는 $4$만큼 지속될 것이다. 즉 $x$를 차이값이라고 하면 $min(x, k)$ 이 해당 $a_i$와 $a_{i+1}$에서 중독 효과가 지속되는 시간이다. 모든 $a_i$, $a_{i + 1}$쌍에 대해서 $min(x, k)$를 더하면 이 값이 바로 $sum(x)$가 되고, 이 값이 $h$보다 큰 경우 답을 갱신하면서 파라매트릭 서치를 진행하면 된다. 그러면 마지막으로 남아있는 right index의 바로 다음 숫자가 답이다.

정답 코드

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

using ll = long long;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        ll h; cin >> h;
        ll a[n];
        for(auto& x : a) cin >> x;
        ll l = 1, r = 1e18;
        while(l <= r){
            ll m = (l + r) / 2;
            ll sum = m;
            for(int i = 0; i < n - 1; i++) sum += min(m, a[i + 1] - a[i]);

            if(sum < h) l = m + 1;
            else r = m - 1;
        }
        cout << r + 1 << "\n";

    }
    return 0;
}