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

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

이제는 그냥 해탈했다. 나는 알고리즘을 못한다. rating이 1000이 넘어가면 그냥 못푼다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 못풀어서 계속 답을 보고 공부하는 과정을 얼마나 반복을 해야하는지 나는 아직도 의문이다. 하지만 뭐 어떡하겠나. 못하는 사람이면 계속 공부하면서 반복 숙달 해야지. 코드포스 문제 1000개를 풀면 그래도 블루는 가지 않을까?
이번 대회에서 배운 것은

1. 제발 A번 문제는 단순하게 생각하자.
2. 제발 침착하게 문제 풀자
3. 진법 개념을 알고리즘 문제에 적용하기

A. Equal or Not Equal (*800)

접기/펼치기

문제 설명
$n$개의 양의 정수가 원형으로 배열되어 있다. $a_1$와 $a_2$가 붙어있고, $a_2$와 $a_3$이 붙어있고, ... $a_{n-1}$과 $a_n$이 붙어있고, $a_n$과 $a_1$이 붙어있다. 그리고 이 숫자를 적고 나서 당신은 인접한 숫자가 서로 같은지 아닌지를 종이에 따로 적었다.

당신이 해야할 것은 인접한 숫자들이 서로 같은지 아닌지를 나타내는 문자열을 보고 이 문자열이 나타내는 상황과 같은 숫자 배열을 만들 수 있는지 판별하는 것이다.

문제 해설
엄청나게 헤맸던 문제이다. 분명 N이나 E의 개수로 간단하게 풀릴거 같은 문제인데 왜 안풀릴까라는 생각을 계속했다. 결국 1시간동안 생각해서 나온 답은 엄청나게 단순한 것이라서 더욱 짜증과 허무함이 생겼던 문제이다.

일단 모두 E로 이루어져 있다면 인접한 모든쌍이 같다는 뜻이고, 당연히 만들 수 있다.
그렇다면 모두 E로 이루어져 있다가 하나면 N이라면 당연히 만들 수 없다. N이 등장하는 순간 숫자가 바뀌는데 다시 원래대로 돌아올 수가 없기 때문이다. 원래대로 돌아와야 하는 이유는 원형이기 때문에.
이와 같은 논리라면 N이 한개만 아니면 반드시 원래 상태로 돌아올 수 있기 때문에 반드시 배열을 만들 수 있다.

정말 쉽죠?

정답 코드

#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 s; cin >> s;
        int cnt = 0;
        for(auto x : s){
            if(x == 'N') cnt++;
        }
        cout << (cnt == 1 ? "NO" : "YES") << "\n";
    }
    return 0;
}

B. Triangles on a Rectangle (*1000)

접기/펼치기

문제 설명
왼쪽 아래에 있는 꼭짓점의 좌표가 $(0, 0)$ 이고, 오른쪽 위에 있는 꼭짓점의 좌표가 $(w, h)$인 직사각형이 축과 평행한 상태로 주어진다.

직사각형의 각 변에 격자점을 찍는 대신, 꼭짓점에는 찍지 않는다. 또한 직사각형의 모든 변에 최소 2개의 점은 찍힌다.

다음 조건을 만족하는 세 점을 선택해야 한다.
* 직사각형의 한 변에서 정확히 두 점을 선택한다.
* 삼각형의 넓이를 최대로 만들어야 한다.

삼각형의 넓이를 2배 한 값을 찾아라.

문제 해설
진짜 개인적으로 A번 문제보다 쉬웠다. 내가 중학교 교육을 받고온건지, 기하문제를 잘 풀어서 그런건지는 모르겠는데 문제를 보자마자 그냥 답이 나왔다. 일단 한 변에서 최대한 멀리 떨어져야 하기 때문에 양 끝점을 선택한다. 이때 문제에서 점은 오름차순으로 주어진다고 했기 때문에 맨 마지막으로 입력된 점에서 맨 처음으로 입력된 점을 빼면 된다. 그리고 삼각형 넒이가 최대가 되기 위해서는 무조건 맞은편 점을 선택해야 하는데, X축과 평행한 변은 그 값이 h일 것이고, Y축과 평행한 변은 그 값이 w일 것이다.

직사각형의 4변에 대해서 가능한 큰 넓이를 모두 구하고 그 값중에서 최대값을 구하면 된다.

정답 코드

#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 w, h; cin >> w >> h;
        long long ans = 0;
        for(int i = 0; i < 4; i++){
            int k, x0, x1; cin >> k >> x0;
            for(int j = 1; j < k; j++) cin >> x1;
            ans = max(ans, 1ll * (x1 - x0) * (i < 2 ? h : w));
        }
        cout << ans << "\n";
    }
    return 0;
}

C. BA-String (*1800)

접기/펼치기

문제 설명
문자 'a'와 '*'로만 이루어져있는 문자열 $s$와 정수 $k$가 주어진다.

각 애스터리스크("*")는 $0$개에서 $k$개 문자 'b'로 바뀔수 있다. 서로 다른 애스터리스크는 'b'문자 개수를 다르게 한다.

변환의 결과를 우리는 BA-string 이라고 한다.

모든 변환할 수 있는 BA-string에서 $x$번째 사전순으로 작은 문자열을 찾아라.

문제 해설
c번 부터 갑자기 *1800문제? 접근하는 방식은 맞았지만 $x$번째를 찾는 방법을 생각해내지 못했고, 그 방식은 바로 진법 변환을 이용하는 것이다.

일단 사전순으로 작은 문자열을 만들기 위해서는 a가 최대한 앞에 있어야한다는 사실은 자명하다. 그렇기 때문에 뒤에서 부터 애스터리스크를 b로 변환해야 할 것이다.
애스터리스크가 3개 있고, $k = 2$라면 문자열은 몇개가 만들어질까? 총 7개이다. 왜냐하면 일단 모든 애스터리스크를 공스트링을 바꾸는 경우 1가지와 각 애스터리스크는 최대 b $2$개씩 만들 수 있기 때문에 6가지가 나온다. 따라서 총 7가지가 나온다.

이것을 일반화 한다면 연속된 애스터리스크가 $x$개 있고, $k$번 변환 할 수 있다면 총 만들 수 있는 문자열은 $x \times k + 1$개 일 것이다.

일단 맨 뒤에있는 애스터리스크부터 바꾸는 것이 맞는데, 개수를 세다가 a를 만나면 개수 세기를 중단하고 그 값을 저장한 다음 다시 0으로 초기화한다. 왜냐하면 a뒤에있는 애스터리스크를 변환하다가 갑자기 a앞에 있는 애스터리스크를 바꾸면 사전순으로 배열이 되지 않기 때문이다. 항상 최적의 방법을 찾아야 한다.

우리는 뒤에서 부터 연속된 애스터리스크의 개수를 세고, a를 만나면 저장후 개수를 초기화한다음 다시 세는 과정을 통해서 개수 배열을 만들었다. 이 배열에는 애스터리스크가 바뀔 수 있는 b string개수가 저장되어 있다.

그러면 만약 $[3, 6, 7]$이렇게 저장되어 있고, 우리는 $20$번째 문자열을 찾으려면 진법을 찾는 방법처럼 하면 된다. 20을 3으로 나눈 나머지는 2, 20을 3으로 나눈 몫은 6이다. 이 몫을 6으로 나눈 나머지는 0, 나눈 몫은 1이다. 이 몫을 7로 나눈 나머지는 1, 몫은 0이다. 이런식으로 구한 나머지를 싹 모아서 자릿수와 맞게 배열하면 $[2, 0, 1]$이 된다. 각각 앞에서부터 1의 자리, 3의 자리, 18의 자리 숫자인 것이다. 이렇게 b를 뒤에서 부터 배열의 앞에서 부터 나오는 숫자만큼 반복하면 답이 된다.

이렇게 진법 변환을 문제를 응용할 수 있다는 점이 이 문제의 핵심인것 같다. 이때 애스터리스크에 b를 아무것도 않은 경우인 가장 사전순으로 작은 문자열인 경우 1가지를 제외하고 구해야한다는 것을 잊지말자.

정답 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
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, k; cin >> n >> k;
        ll x; cin >> x;
        string s; cin >> s;
        vector<ll> cnt;
        int num = 0;
        for(int i = s.size() - 1; i >= 0; i--){
            if(s[i] == '*') num++;
            else{
                if(num > 0) cnt.push_back(num * k + 1), num = 0;
            }
        }
        if(num > 0) cnt.push_back(num * k + 1);
        vector<ll> ans;
        x--;
        for(auto i : cnt){
            ans.push_back(x % i);
            x /= i;
        }
        reverse(ans.begin(), ans.end());
        bool flag = true;
        int idx = 0;
        for(auto c : s){
            if(c == 'a') cout << "a", flag = true;
            else{
                if(flag) cout << string(ans[idx++], 'b'), flag = false;
            }
        }
        cout << "\n";
    }
    return 0;
}