Codeforces Round #761 (Div. 2) A부터 C까지 업솔빙

Codeforces Round #761 (Div. 2) A부터 C까지 업솔빙

유난히 case-work가 많은 문제셋이였다. A번부터 3가지 정도 경우의 수를 고민했어야 하는문제, B번은 구성적, C번은 코드포스에서 자주 나오는 유형인 정렬 + 그리디 + index 배열 + 나머지 연산의 성질 문제였다. 하지만 못풀었다. 이제 익숙해서 문제 풀 수 있어야 되는데, 왜 못풀지? 난 아직도 모르겠다. 이제는 그냥 포기 안하고 계속 문제푸는 것을 목표로 하려고한다.
이번 대회에서 배운 것은

1. while문의 활용
2. 나머지연산의 최댓값
3. sort와 위치바꾸기

A. Forbidden Subsequence (*800)

접기/펼치기

문제 설명
영어 소문자로만 이루어진 문자열 $S$와 $T$가 주어진다. $T$는 문자열 $abc$로 이루어진 순열이다.

$S$의 사전순으로 가장 작은 순열 $S'$를 구하시오, 이때 $T$는 $S'$의 subseqence가 아니어야 한다.

문제 해설
$T$의 경우의 수가 6가지 나오는 것을 보고, 경우의 수를 나누면 해결될 문제라고 생각했다. 단순히 $S$의 사전순으로 가장 작은 순열을 얻기 위해서는 그냥 정렬을 하면 될 것이다. 그런데 여기서 고려해야할 점이 2가지 있다. 일단 $T$가 $abc$인 경우이다. 그러면 그냥 정렬을 할 때, $S$에 $a, b, c$가 다 있다면 무조건 $abc$를 subseqence로 가질 것이다. 그러면 두번째로 작은 $b$와 세번째로 작은 $c$의 위치를 단순히 바꾸면 된다. 그런데 만약 $T$가 $abc$인데, $s$에 $a, b, c$가 모두 들어가 있지 않다면? 이럴때는 또 그냥 정렬을 하면 답이 된다.

즉 $T = abc$이며, $S$에 $a, b, c$가 모두 존재하다면 $b$와 $c$의 위치를 바꾸고 그렇지 않으면 그냥 정렬을 해서 출력하면 된다. $a, b, c$가 모두 존재하다는 것을 어떻게알까? 그냥 배열을 이용해서 일일이 확인하는 방법도 있지만, 맨 앞에 $a$가 있으면 그냥 $b$의 위치와 $c$의 위치를 바꾸라는 식으로 코딩을 하면된다. $a, b, c$가 다 있다면 두 문자열의 위치를 바꿀 것이고, 그렇지 않으면 그냥 둘 것이다.

정답 코드

#include <iostream>
#include <string>
#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--){
        string s, t; cin >> s >> t;
        sort(s.begin(), s.end());
        if(t == "abc" && s[0] == 'a'){
            sort(lower_bound(s.begin(), s.end(), 'b'), upper_bound(s.begin(), s.end(), 'c'), greater<>());
        }
        cout << s << "\n";
    }
    return 0;
}

B. GCD Problem (*900)

접기/펼치기

문제 설명
양수 $n$이 주어진다. $a + b + c = n$ 이고 $gcd(a, b) = c$인 세 서로 다른 양수 $a, b, c$를 구하라.

문제 해설
그냥 진짜 노가다문제, 이게 구성적 문제 기본이지. 일단 직관으로 $c$가 $1$이어야 문제를 푸는데 편하게 풀 수 있을 것 같다. 그러면 $a + b = n - 1$이면서 $gcd(a, b) = 1$인 $a, b$를 구해야한다.

일단 $n - 1 = k$이 홀수이면 $a = k, b = k + 1$ 이렇게 하면 무조건 성립한다.
$n - 1 = k$가 짝수이면 위의 방식대로 할 수 없다. 그래서 추가적으로 생각을 해야한다.
$k / 2$가 홀수이면 각각 $1$을 더하고 $1$을 빼면 둘다 짝수가 돼서 $gcd(a, b) = 2$가 된다. 그래서 이때는 $2$씩 빼고, 더해서 홀수로 만든다.
$k / 2$가 짝수라면 각각 $1$을 더하고 빼도 둘다 홀수가 되서 $gcd(a, b) = 1$이 된다.

정답 코드

#include <iostream>
#include <string>
#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;
        n--;
        if(n & 1) cout << n / 2 << " " << n / 2 + 1 << " " << 1;
        else{
            n >>= 1;
            if(n & 1) cout << n - 2 << " " << n + 2 << " " << 1;
            else cout << n - 1 << " " << n + 1 << " " << 1;
        }
        cout << "\n";
    }
    return 0;
}

C. Paprika and Permutation (*1300)

접기/펼치기

문제 설명
지젤은 순열을 사랑한다. 지젤은 배열 $a = [a_1, a_2, ..., a_n]$을 가지고 있다. 이 배열을 $1$부터 $n$까지 순열로 만들고 싶다.

이 목표를 달성하기 위해서 배열에서 연산을 수행해야 한다. 각 연산은 다음과 같다.

• 두 정수 $i (1 \le i \le n)$과 $x (x > 0)$을 선택하고, $a_i := a_i\;mod\;x$를 수행한다.

주어진 배열을 $1$부터 $n$까지 순열로 만들기 위해서 필요한 최소 연산의 개수를 구하라. 만약 불가능하다면 $-1$을 출력하라.

문제 해설
일단 이 문제를 풀기위해서는 다음 성질을 알아야 한다.

• $x\;mod\;y < x / 2 (x >= y)$
• $x\;mod\;y = x (x < y)$

이 두 성질 중에서 나는 첫번째 성질을 사용해서 이 문제를 풀 것이다. 우리의 목표는 숫자를 바꾸는 것인데, 숫자가 그대로가 되는 성질 2는 필요가 없기 때문이다.

나머지 연산을 하면 반드시 숫자가 작아지기 때문에 순열의 작은 숫자 $1, 2, ...$를 구하기 위해서 $a_i$도 작은 순서대로 정렬을 하고 구하는 것이 가장 최선이라는 생각이 들 것이다. 그래서 일단 $a$를 정렬한다. 그리고 이미 $a_i$가 $1$부터 $n$까지 숫자이면 별도의 연산이 필요 없기 때문에 그냥 두어야 한다는 것도 생각해야 한다. 그래서 나는 $a_i$가 $1$부터 $n$까지 숫자이면 따로 배열에 저장해두고, $1$부터 $n$까지 2번 이상 등장하거나 그 밖에 있는 수만을 따로 저장해서 정렬했다. $1$부터 $n$까지 숫자는 한번만 등장하고 나머지 숫자는 필요가 없기 때문이다.

그러면 이제 맨 앞부터 확인한다. 이때 이미 $1$부터 $n$까지 숫자가 존재하는 경우는 pass하고, 비어있는 순열 자리에 대해서 연산을 수행한다. $a_i\;mod\;x$은 반드시 $a_i / 2$ 보다 작은 값이 나온다. 즉 현재 필요한 순열 자리인 $k$가 $a_i / 2$보다 크거나 같다면 무조건 $k$를 만들 수 없다. 이런 경우가 하나라도 나온다면 바로 false를 저장하고 프로그램을 종료하면 된다. 모든 조건문을 통과하면 배열에 저장되어 있는 $1$부터 $n$이 아닌 값의 수 만큼 연산을 반드시 진행해야 하므로 해당 배열의 원소 개수를 출력한다.

정답 코드

#include <iostream>
#include <vector>
#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;
        vector<int> cnt(n + 1), a;
        for(int i = 0; i < n; i++){
            int num; cin >> num;
            if(num <= n && cnt[num] == 0) cnt[num]++;
            else a.push_back(num);
        }
        sort(a.begin(), a.end());
        int pos = 1;
        bool flag = true;
        for(int i = 0; i < a.size(); i++){
            while(cnt[pos]) pos++;
            if(a[i] <= 2 * pos) flag = false;
            pos++;
        }
        cout << (flag ? (int)a.size() : -1) << "\n";
    }
    return 0;
}