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

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

C번문제를 거의 다 풀었다고 생각했는데, 쉬울듯 말듯 계속 풀게만드는 문제라서 애먹었다. DIV 2 3솔의 벽은 높은것 같다. 그래도 *1100문제를 풀어서 다행이다. 이제 진짜 B번 문제는 좀 감이 잡히는 것 같아서 기분이 좋은 하루이다.

A. Equidistant Letters (*800)

접기/펼치기

문제 설명
알파벳 소문자로 이루어진 문자열 $s$가 주어진다. 각 문자는 2번보다 더 많이 등장하지 않는다.

너의 목표는 같은 문자사이의 거리를 모두 같게 문자열에 있는 문자를 재배열 하는 것이다. 이때 문자를 새로 추가하거나 제거할 수 없다.

문제 해설
같은 문자사이의 거리를 모두 같게 만드는데 여기서 같은 문자는 최대 2개까지 밖에 없다는 조건을 걸었다. 즉 그냥 정렬을 하면 같은 문자사이 거리가 모두 1이되게 재배열 할 수 있다.

정답 코드

#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--){
        string s; cin >> s;
        sort(s.begin(), s.end());
        cout << s << "\n";
    }
    return 0;
}

B. Minor Reduction (*1100)

접기/펼치기

문제 설명
맨 앞이 $0$이 아닌 10진수 숫자 $x$가 주어진다.

다음 축소방법을 정확히 한번만 수행할 수 있다.

• $x$의 서로 인접한 자릿수 2개를 선택한 후 그 자리를 서로 인접한 자릿수의 합으로 바꾼다.

위 연산을 통해서 얻을 수 있는 숫자 중 가장 큰 수는 무엇인가?

문제 해설
맨 처음에는 그냥 완전탐색으로 풀려고 했는데, 그러면 정렬을 할 때 가장 작은 숫자를 찾을 수가 없다. 왜냐하면 문제 조건에 $0$이 20만개 있는 수까지가 제한인데, 이 숫자를 다루기 위해서는 문자열을 사용해야하고, 문자열의 정렬방식은 사전순으로 정렬하기 때문에 정수로 정렬하는 방식과 다르다.

그렇기 때문에 나는 그리디 알고리즘 방식으로 접근했다.
일단 먼저 알 수 있는 것은 인접한 두 자릿수를 더할 때 10이 넘으면 무조건 이득이 된다는 점이다. 그러면 10이 넘는 자릿수가 여러개라면? 무조건 작은 자릿수부터 확인해야 최적의 해이다. 왜냐하면 두 수를 더해서 10이 넘는 경우는 더했을 때, 크기에서 손해가 되기 때문에 그 손해를 최소화해야하고, 그렇게 하기 위해서는 최대한 작은 자리에서 수행해야 그 손해를 최소화 할 수 있다.

만약 10이 넘는 두 수의 쌍이 없다면 어떻게 해야할까? 그러면 무조건 맨 앞에 두 숫자를 더하는 것이 최적해이다. 이번에 10이 넘지 않는 두 수의 쌍인 경우, 더하면 오히려 더 이득이기 때문이다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t; cin >> t;
    while(t--){
        string s; cin >> s;
        bool flag = true;
        for(int i = s.size() - 1; i > 0; i--){
            if(s[i] - '0' + s[i - 1] - '0' > 9){
                cout << s.substr(0, i - 1) + to_string(s[i] - '0' + s[i - 1] - '0') + s.substr(i + 1);
                flag = false;
                break;
            }
        }
        if(flag) cout << to_string(s[0] - '0' + s[1] - '0') + s.substr(2);
        cout << "\n";
    }
    return 0;
}

C. Monsters And Spells (*1700)

접기/펼치기

문제 설명
한수는 컴퓨터게임을 하고 있다. 그는 마법사 직업을 플레이 하고 있는데, 이 직업은 오직 1개 마법만 배웠다. 운 좋게 이 마법은 몬스터에게 데미지를 주는 마법이다.

이 단계에서 한수는 $n$개의 몬스터를 만나고, $i$번째 몬스터는 게임을 시작한지 $k_i$초 뒤에 등장하고, $h_i$의 체력을 가지고 있다. 추가적으로 모든 $1 \le i \le n$ 에 대해서 $h_i \le k_i$이다. 또한 모든 $k_i$는 서로 다르다.

한수는 1초에 한번씩 마법을 발동할 수 있다. 이 마법의 데미지는 다음과 같이 계산한다.

1. 만약 이전 초에 마법을 발동하지 않았다면 이번 초의 데미지는 1이다.
2. 그렇지 않으면 이전 초에 데미지가 $x$라면 이번 데미지는 $1$과 $x + 1$중에서 하나를 선택할 수 있다.

이 마법은 발동하기 위해서 마나가 필요한다. $x$데미지를 주면 마나 $x$가 필요하다. 마나는 회복되지 않는다.

$i$번째 몬스터를 죽이기 위해서는 한수는 $k_i$초에 최소한 데미지를 $h_i$이상 주어야 한다.

또한 한수는 몬스터가 없는 초에도 마법을 발동할 수 있다.

한수가 모든 몬스터를 죽이기 위해서 필요한 최소 마나를 구하라.

문제 해설
결국 못푼 문제였다. 이렇게 풀면 어떨까? 결국 최소 마나가 필요하기 때문에 몬스터가 $k_i$초에 체력이 $h_i$인 상태로 등장한다면 $k_i - h_i + 1$ 초부터 마법을 발동해서 $k_i$초까지 계속 발동하면 되고, 그때 필요한 마나의 양은 등차수열 공식을 사용해서 $(k_i - h_i) * (k_i - h_i + 1) / 2$ 이다.

그러면 구간을 이렇게 나누면 어떨까? 열린구간을 사용해서 $(k_i - h_i, k_i]$ 이면 왼쪽의 $k_i - h_i$은 포함하지 않기 때문에 이렇게 설정해도 된다.

일단 두개의 구간이 서로 겹치지 않는다면 그냥 따로따로 등차수열 공식을 사용해 값을 구해서 더하면 된다. 만약 두개의 구간이 서로 겹친다면? 두개의 구간중 오른쪽 값이 큰것을 맨 오른쪽 구간으로 정하고 두 구간을 합치면 된다. 이런 알고리즘을 사용하면 쉽게 답을 구할 수 있다. 즉 각 초마다 구간을 구하고, 정렬을 한 뒤에 위 두 경우에 따라 케이스 분류를 하면 된다. 이때 구간을 합칠땐 값을 더하면 안된다. 왜냐하면 합치고 난 뒤에 또 나타나는 구간이 또 겹치는 경우일 수 있기 때문이다.

정답 코드

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

using ll = long long;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        ll k[n], h[n];
        for(auto& x : k) cin >> x;
        for(auto& x : h) cin >> x;
        vector<pair<ll, ll>> v;
        for(int i = 0; i < n; i++) v.push_back({k[i] - h[i], k[i]});
        sort(v.begin(), v.end());
        ll l = -1, r = -1, ans = 0;
        for(auto [x, y] : v){
            if(r <= x){
                ans += (r - l) * (r - l + 1) / 2LL;
                l = x;
                r = y;
            }
            else r = max(r, y);
        }
        ans += (r - l) * (r - l + 1) / 2LL;
        cout << ans << "\n";
    }
    return 0;
}