Codeforces Round #753 (Div. 3) A부터 D까지 업솔빙

Codeforces Round #753 (Div. 3) A부터 D까지 업솔빙

이번 대회에는 DIV. 3답게 C번까지 풀었지만 D번은 못풀었는데, 내가 마지막에 제출한 틀린 코드에서 pair에 정렬 순서만 바꾸면 풀리는 문제라서 이제는 D번을 풀 수 있는 단계까지 눈앞에 이르렀다. E번 문제는 빡 구현문제인데 원래라면 업솔빙 했어야 하지만 codefore와 atcoder에서 내가 당장 배워야 하는 것은 dp, greedy, constructive, math, implementation, number theory 이기 때문에 pass했다. 이번 대회에서 배운 것은

1. 규칙을 찾는 문제에서는 문제가 하라는 대로 일단 처음 10개항은 써보기
2. 잘 모르겠어도 끝까지 포기하지 말기
3. 접근법이 잘못된 것 같으면 과감히 방향을 틀기

A. Linear Keyboard (*800)

접기/펼치기

문제 설명
26개 키로 구성되어있는 키보드가 주어진다. 키는 한줄에 특정한 순서로 일렬로 늘여있고 각 키는 모두 서로 다른 알파벳 소문자로 이루어져 있다. 우리는 이 키보드로 단어 $s$를 쳐야한다.

이 단어를 치기 위해서는 각각의 문자를 하나씩 순서대로 입력해야 한다. 각 문자를 입력하기 위해서는 그 문자의 정확한 위치로 손을 움직이고 눌러야 한다.

키 사이를 움직이는 것은 이 키들 사이에 있는 위치 차이의 절대값만큼 시간이 걸린다. 단어의 첫번째 문자를 입력할 때는 시간이 걸리지 않는다.

단어 $s$를 입력하기 위해서 걸리는 총 시간을 구하시오.

문제 해설
문제에서 주어진 키의 위치를 찾아내서 각 키 사이의 절댓값을 출력하면 되는 문제이다. 이 문제에서 핵심은 주어진 키의 위치를 찾는 것이다. 문제에서는 std::find를 사용해서 찾으라고 하는데, 다른 사람의 코드를 보니 결국 소문자 a부터 z는 아스키코드 128안에 다 들어가기 때문에 배열을 128개 선언해서 문자 자체를 index로 하는 위치 배열을 만들어서 푸는 사람이 있었고 이 사람의 방식이 좋은것 같아서 공부한다.

정답 코드

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

int alpha[128];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        string s; cin >> s;
        for(int i = 0; i < s.size(); i++) alpha[s[i]] = i;
        string a; cin >> a;
        int ans = 0;
        for(int i = 0; i < a.size() - 1; i++) ans += abs(alpha[a[i + 1]] - alpha[a[i]]);
        cout << ans << "\n";
    }
    return 0;
}

B. Odd Grasshopper (*900)

접기/펼치기

문제 설명
메뚜기는 수직선 좌표 $x_0$에 위치해있다.

메뚜기는 점프를 하는데 현재 위치해있는 좌표의 홀/짝에 의해서 방향이 결정된다. 만약 현재 메뚜기가 위치한 좌표가 홀수라면 오른쪽으로 점프하고 현재 위치한 좌표가 짝수라면 왼쪽으로 점프한다.

이 메뚜기는 정확히 $i$분 후에 거리 $i$만큼 점프를 한다. 만약 $3$분이 지나면 메뚜기가 점프한 총 거리는 $1 + 2 + 3 = 6$이 된다.

메뚜기가 정확히 $n$분이 지났을 때 메뚜기가 위치한 좌표값을 구하시오.

문제 해설
문제에서 주어지는 제약이 $(0 \le n \le 10^{14})$ 이므로 일반적인 for문을 사용해서는 풀 수 없다는 것을 알수 있고 결국 수학이나 규칙을 찾아서 한번에 계산해야하는 문제이다.

규칙을 찾기 위해서 가장 쉬운 방법은 바로 나열하기이다. 처음 위치를 0이라고 하면 첫 4분동안 점프를 하면 메뚜기의 위치는 $-1, 1, 4, 0$ 이 된다. 첫 8분동안 점프를 하면 메뚜기의 위치는 $-1, 1, 4, 0, -5, 1, 8, 0$ 이 된다. 4의 배수에 계속 0이 등장하는 것이 보이는가? 결국 메뚜기가 4의 배수만큼 점프를 한다면 최종적인 위치는 $0$ 이 된다는 규칙을 발견했다.

주어진 횟수 $n$에 가장 가까운 4의 배수를 구하면 이 수분 까지 점프를 하면 메뚜기의 위치는 $0$이 된다. 그 다음 숫자만큼 위에서 말한 규칙대로 점프를 진행하면 답을 구할 수 있다. $n$을 4로 나눈 나머지 값만큼 반복문을 실행할 텐데 최대 3번만 반복문을 실행하므로 절대 시간초과가 날 수가 없다.

정답 코드

#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--){
        long long x0, n; cin >> x0 >> n;
        for(long long i = (n / 4) * 4 + 1; i <= n; i++) x0 += (x0 & 1 ? i : -i);
        cout << x0 << "\n";
    }
    return 0;
}

C. Minimum Extraction (*1000)

접기/펼치기

문제 설명
$n$개의 정수로 이루어진 배열 $a$가 주어진다.

$a$의 길이가 $1$보다 크다면 minimum extraction 이라는 연산을 할 수 있다.

1. 배열에서 가장 작은 숫자 $m$을 선택한다. 만약 가장 작은 숫자가 여러개 있다면 아무거나 선택한다.
2. 배열에서 $m$을 제거하고, 남은 모든 원소에 $m$을 뺀다.

따라서 각 연산을 계속 하면 배열의 길이는 결국 $1$이 될 것이다.

우리가 찾아야 할 것은 minimum extraction 연산을 계속 하면서 나오는 숫자 $m$의 최댓값을 구하는 것이다.

문제 해설
이 문제도 규칙을 찾으면 쉽게 풀 수 있다. 규칙을 찾으려면 문제에서 말하는 minimum extraction 연산을 직접 수행해 봐야한다.

배열 $a$를 $a = [a_0, a_1, a_2, a_3]$ 이라고 해보자. 일단 이 배열에서 가장 작은 값을 찾아야 하는데 당장 떠오르는 것은 std::min_element 함수이다. 하지만 이 함수는 시간 복잡도가 $O(n)$ 이므로 $n \le 2 \cdot 10^5$ 일때 반드시 시간초과가 난다. 그렇다면 이 배열을 오름차순으로 정렬하면 어떨까? 맨 앞에 있는 원소가 최솟값이 되고, 뒤에 있는 나머지 원소에 최솟값을 빼고 맨 앞에 있는 원소를 무시해도 두번째 위치한 원소가 다음 연산의 최솟값이 계속 된다. 따라서 정렬을 하면 이 문제를 시간제한에 걸리지 않게 풀 수 있을 것이다.

• 첫번째 연산을 해보자. 가장 작은 수는 $a_0$이고 뺀 결과 배열은 $[a_1 - a_0, a_2 - a_0, a_3 - a_0]$ 이다.
• 두번째 연산을 해보자. 가장 작은 수는 $a_1 - a_0$이고 뺀 결과 배열은 $[a_2 - a_0 - (a_1 - a_0), a_3 - a_0 - (a_1 - a_0)]$ 이다.
• 세번째 연산을 해보자. 가장 작은 수는 $a_2 - a_0 - (a_1 - a_0) = a_2 - a_1$이다. 여기서 부터 뭔가 느낌이 이상하다. 뺀 결과 배열은 $[a_3 - a_0 - (a_1 - a_0) - (a_2 - a_1)]$ 이고 이 값은 $a_3 - a_2$ 이다.

즉 그냥 최솟값 $m$은 $a_i - a_{i - 1}$이다. 따라서 배열을 정렬한 다음에 저 값중 max값을 구하면 답이 나온다.

정답 코드

#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);
        int ans = a[0];
        for(int i = 1; i < n; i++) ans = max(ans, a[i] - a[i - 1]);
        cout << ans << "\n";
    }
    return 0;
}

D. Blue-Red Permutation (*1300)

접기/펼치기

문제 설명
길이가 $n$인 배열 $a$가 주어진다. 배열의 각 원소는 서로 같을 수 있다.

배열의 각 원소는 파란색 혹은 빨간색으로 칠해져 있다. 배열에 색깔이 칠해져 있지 않은 원소는 없다. 아래에 있는 두 연산 중 하나의 연산을 각 단계마다 사용할 수 있다.

• 아무 파란색으로 색칠된 원소를 선택해서 값을 $1$ 내린다.
• 아무 빨간색으로 색칠된 원소를 선택해서 값을 $1$ 올린다.

만약 한 원소가 모두 빨간색, 혹은 모두 파란색으로 색칠되어 있다면 나머지 한 연산은 사용할 수 없을 것이다.

우리는 위에 있는 연산을 0번 혹은 그 이상 수행해서 배열의 결과 값이 $1$부터 $n$ 까지 순열이 될 수 있는지 없는지 판독해야 한다.

문제 해설
문제에서 요구하는 정해와 거의 일치하지만 pair vector의 정렬 순서 차이가 문제의 AC, REJECT 여부를 만든 것 같다.

이 문제에서 핵심은 파란색과 빨간색으로 색칠된 원소의 특징을 알아내야 하는 것이다. 파란색으로 색칠된 원소는 그 값을 넘어서는 절대 만들 수 없다. 반대로 빨간색으로 색칠된 원소는 그 값보다 작은 값으로는 절대 될 수 없다. 만약에 우리가 이 배열을 색깔값과 원소값을 한번에 묶어서 정렬을 한다면 원소 값이 오름차순으로 배열될 것이다.

파란색으로 색칠된 값은 그 값보다 작은 수를 모두 만들 수 있기 때문에 오름차순 중에서 앞에 배치하면 더 많이 사용할 수 있을 것이다. 반대로 빨간색으로 색칠된 값은 그 값보다 큰 수를 모두 만들 수 있기 때문에 오름차순 중에서 뒤에 배치하면 더 많이 사용할 수 있을 것이다. 즉 작은 값이 만들어 질수 있는 파란색 원소를 앞에 배치하고 그 원소중에서 오름차순으로 배치한다면 차례대로 그 값이 $1$부터 $n$이 될 수 있는지 검사하고 하나라도 조건에 안맞는다면 false를 출력하고 break를 하면 된다.
만약 $2$ 가 나와야 하는데 빨간색 $3$이 등장한다면? 절대 $2$를 만들 수 없다. 하지만 파란색 $5$가 등장한다면 만들 수 있다. 우리가 오름차순으로 배열을 정렬했기 때문에 자신보다 작은 값만 만들 수 있는 파란색을 먼저 사용해야 뒤에 나오는 큰 수를 빨간색 원소를 이용해서 만들 수 있다. 그래서 우리가 색깔로 먼저 정렬을 한 이유이다.

나는 처음 문제를 풀때 원소값을 우선 순위로 정렬을 했더니 빨간색, 파란색이 모두 섞여버려서 문제를 못풀었다. 진짜 조금만 남은 것 같다. 뉴비 탈출!!

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
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;
        vector<pair<char, int>> v;
        for(int i = 0; i < n; i++){
            char c; cin >> c;
            v.push_back({c, a[i]});
        }
        sort(v.begin(), v.end());
        bool flag = true;
        for(int i = 0; i < n; i++){
            if(v[i].first == 'B' && v[i].second < i + 1) flag = false;
            if(v[i].first == 'R' && v[i].second > i + 1) flag = false;
        }
        cout << (flag ? "yes" : "no") << "\n";
    }
    return 0;
}