Codeforces Round #756 A부터 C까지 업솔빙

Codeforces Round #756 A부터 C까지 업솔빙

알고리즘 놓은지 1달이 되서 다시 잡은 코드포스이다. 내가 코드포스에서 나오는 문제 유형을 잘 못하는걸로 결론을 내렸다. 하지만 내가 잘 못하는 것을 계속 손 놓고 있으면 그 분야는 계속 못하게 된다. 잘 몰라도 계속 붙잡는것이 필요한 순간. 언젠간 성장하겠지.

A. Make Even (*800)

접기/펼치기

문제 설명
창록이에게 $0$이 없는 정수 $n$이 주어진다. 다음 연산을 몇번이고 수행할 수 있다.

• 왼쪽부터 길이 $l$만큼 $n$의 부분 문자열을 선택한다. 그리고 이 부분 문자열을 뒤집은 다음 원래 자리에 둔다.

창록이는 짝수를 좋아한다. 따라서 이 숫자를 짝수로 만들고 싶다. 그리고 그는 참을성이 별로 없기 때문에 가능한 적은 연산으로 짝수를 만들고 싶다.

숫자 $n$을 짝수로 만들기 위해서 필요한 최소 연산의 개수를 구하라. 만약 불가능하다면 -1을 출력한다.

문제 해설

1. 한 숫자가 짝수가 되기 위해서는 맨 뒤 자리 숫자가 짝수여야 한다.
2. 맨 뒤 자리 숫자가 짝수가 아니라면 맨 앞자리 숫자가 짝수이면 전체 숫자를 1번만 뒤집으면 된다.
3. 맨 앞, 맨 뒤자리 숫자가 짝수가 아니라면 전체 숫자에 짝수가 있다면 그 짝수까지 부분 문자열을 선택해서 한번 뒤집는다. 그러면 짝수가 맨 앞에 온다. 그리고 전체 숫자를 1번만 뒤집으면 되고, 총 2번의 최소 연산이 필요하다.
4. 숫자에 짝수가 1개도 없다면 -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;
        if((s.back() - '0') % 2 == 0){
            cout << 0 << "\n";
            continue;
        }

        if((s.front() - '0') % 2 == 0){
            cout << 1 << "\n";
            continue;
        }

        bool fg = false;
        for(auto c : s){
            if((c - '0') % 2 == 0) fg = true;
        }
        cout << (fg ? 2 : -1) << "\n";
    }
    return 0;
}

B. Team Composition: Programmers and Mathematicians (*800)

접기/펼치기

문제 설명
프로그래머 $a$명과 수학자 $b$명이 있다. 이 사람들끼리 다음 조건을 만족해서 팀을 최대로 만드는 것이 목표이다.

• 각 팀은 정확히 4명으로 이루어져 있다.
• 한 팀에 프로그래머 4명, 혹은 수학자 4명으로만 이루어지면 안된다.

따라서 한 팀에는 반드시 최소 1명의 프로그래머와 1명의 수학자가 있어야 한다.

이 사람들로 만들 수 있는 최대 팀 개수를 구하시오.

문제 해설
요런 수학문제는 너무 어렵다. 일단 일관성을 유지하기 위해서 항상 $a \le b$이 상태라고 가정하자. $a > b$인 경우에는 swap을 해준다. 항상 $a$가 작다고 가정을 했기 때문에 $a$의 기준으로 팀을 맞출 수 밖에 없다. 만약 $3 \times a \le b$인 경우에는 답이 항상 $a$이다. 이때 이 결론이 나온 이유는 $a$팀을 1명씩, $b$팀을 3명씩 묶었을때 나온 결과이다.

저 위에 경우가 아니라면 1명, 3명씩만 묶는것이 아니라 2명, 2명씩 묶는 경우도 생각해줘야하는데 2명, 2명씩 묶는 경우 최적의 해를 위해서 1명, 3명씩 묶고 남은 사람이 서로 같아야 한다. 따라서 $a - k = b - 3 \times k$ 등식을 만족해야하고, 식을 풀면 $k = (b - a) / 2$가 된다. 그러면 1명, 3명씩 짝지어서 만든 팀이 총 $k$개가 있고, 남은 인원수가 $a - k$, $b - 3 \times k$명이 각각있다. 우리는 이 두 팀을 2명씩 짝지어서 만들것이기 때문에 $min(a - k, b - 3 \times k) / 2$ 개의 팀을 추가로 만들 수 있고, $k$와 저 수를 더하면 답이 된다.

정답 코드

#include <bits/stdc++.h>
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--){
        ll a, b; cin >> a >> b;
        if(a > b) swap(a, b);
        if(3 * a <= b) cout << a << "\n";
        else{
            ll k = (b - a) >> 1;
            cout << k + min(a - k, b - 3 * k) / 2 << "\n";
        }
    }
    return 0;
}

C. Polycarp Recovers the Permutation (*1000)

접기/펼치기

문제 설명
길이가 $n$인 수열 $p$가 주어진다. 그리고 길이가 $0$인 빈 수열 $a$가 주어진다. 다음 단계를 정확히 $n$번 수행해야 한다.

• $p$의 가장 왼쪽 숫자와 가장 오른쪽 숫자를 보고 둘 중에 작은 숫자를 고른다.
• $p$의 가장 왼쪽 숫자를 골랐다면 $a$의 왼쪽에 그 숫자를 추가하고, 그렇지 않으면 $a$의 오른쪽에 그 숫자를 추가한다.
• 선택한 숫자는 $p$에서 지운다.

여기서 마지막 단계에서 $p$는 길이가 $1$이기 때문에 가장 작은 숫자는 맨 왼쪽, 맨 오른쪽 둘다 만족한다. 따라서 이때는 이 마지막 숫자를 맨 앞이나 맨 뒤 아무곳이나 넣어도 된다.

최종 결과 배열인 $a$가 주어진다. $a$를 만들 수 있는 배열 $p$를 찾아라. 만약 $p$가 여러가지인 경우 그중 하나를 출력하고 불가능 하다면 -1을 출력하라.

문제 해설
구성적 문제이다. 이런 문제는 규칙을 찾으면 10분컷 할 수 있지만 안보인다면 영원히 못푸는 문제이다. 이런 문제를 어떻게 빨리 규칙을 찾을 수 있을까? 나는 잘 모르겠다. 연습만이 살길.

반드시 찾아야 하는 문제의 핵심은 가장 큰 숫자가 항상 마지막에 남는다는 것이다. 왜냐하면 양 끝에서 작은 숫자를 골라서 빼내기 때문에 결국은 가장 큰 숫자가 마지막에 남는다. 따라서 반드시 한 순열에서 가장 큰 숫자가 맨 앞이나 맨 뒤에 존재해야 하고, 그렇지 않으면 해당 수열은 만들 수 없다.

가장 큰 숫자가 맨 앞이나 맨 뒤에 존재하는 경우에서 어떻게 $p$를 찾을 수 있을까? 가장 큰 숫자가 맨 앞, 맨 뒤에 있다는 것이 곧 이 문제의 키 포인트 되겠다. $a$를 반대로 뒤집으면 해당 수열을 구할 수 있다. 이 결론은 구성적 문제 답게 몇가지 예시를 들어서 확인해보면 답이 맞다는 것을 알 수 있다.

정답 코드

#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--){
        int n; cin >> n;
        int a[n];
        for(auto& x : a) cin >> x;
        if(a[0] != n && a[n - 1] != n){
            cout << -1 << "\n";
            continue;
        }

        for(int i = n - 1; i >= 0; i--) cout << a[i] << " ";
        cout << "\n";
    }
    return 0;
}