Educational Codeforces Round 120 A부터 B까지 업솔빙

Educational Codeforces Round 120 A부터 B까지 업솔빙

C번 문제가 너무 어려워서 패스. 이분탐색 문제인데 좀 더 복잡한 수학이 결합되어 그런지 이해하기 어려웠다. 너무 배끼는 듯한 느낌이 들어서 업솔빙하는게 아니라는 판단이 들어 이번에는 B까지만 업솔빙 하려한다.

A. Construct a Rectangle (*800)

접기/펼치기

문제 설명
길이가 $l_1, l_2, l_3$인 세 막대기가 있다.

이 막대기중 하나를 부숴 다음 조건을 맞춰 두 조각으로 만든다.

• 두 조각은 양수 길이이다.
• 두 조각의 합은 원래 부수기전 막대기의 길이와 같다.
• 만들어진 4개의 조각으로 각각 사각형의 한 변으로 사용해 정확히 직사각형을 만들 수 있다.

막대기의 길이가 주어졌을때 위의 조건을 만족하는지 판단하라.

문제 해설
쉬운 아이디어 문제이다. 일단 한 막대기의 길이가 나머지 두 막대기의 길이 합과 같으면 반드시 직사각형을 만들 수 있다.
이 경우 뿐만 아니라 다른 경우도 가능한데, 두 막대기의 길이가 같고 남은 막대기의 길이가 짝수라면 길이가 같은 막대기 끼리 평행한 두 변을 만들 수 있고, 길이가 짝수인 막대기를 반으로 부숴서 나머지 두 변을 만들 수 있다.

위의 조건을 모두 구현하면 끝.

정답 코드

#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 a, b, c; cin >> a >> b >> c;
        if(a == b + c || b == a + c || c == a + b) cout << "yes";
        else if((a == b && c % 2 == 0) || (b == c && a % 2 == 0) || (a == c && b % 2 == 0)) cout << "yes";
        else cout << "no";
        cout << "\n";
    }
    return 0;
}

B. Berland Music (*1000)

접기/펼치기

문제 설명
베를린 뮤직은 베를린 지역 음악가를 지원하기 위해서 만들어진 음악 스트리밍 서비스이다. 이 서비스의 개발자는 현재 노래 추천 모듈을 개발 중이다.

그래서 현수가 노래 $n$곡을 추천한다고 상상해보자. 각 노래는 $1$ 부터 $n$까지 번호가 부여되고, $i$번째 노래는 예상 순위 $p_i$가 주어진다. 이 순위는 $1$부터 $n$까지 순열로 이루어져 있다.

이 노래를 다 듣고 나서 현수는 각 노래에 좋아요 버튼이나 싫어요 버튼을 누른다. 그가 한 투표 수열은 문자열 $s$로 표현되는데, $s_i = 0$이면 $i$번째 노래에 싫어요를 누르는 것이고, $s_i = 1$이면 좋아요를 누른 것이다.

이 서비스는 원래 노래의 순위를 다음 방식으로 재평가 하는 것이다.

• 새로운 순위 $q_1, q_2, ..., q_n$은 여전히 순열이다.
• 현수가 좋아요를 누른 모든 노래는 현수가 싫어요를 누른 모든 노래보다 반드시 높은 순위를 가져야 한다.

모든 가능한 순열 중에서 $p$와 $q$의 편차에 절댓값을 씌운 값의 모든 합이 가장 작은 순열을 찾아라.

문제 해설
생각보다 쉽게 해결 방법이 떠오른 문제이다. 이번 문제처럼 쉽고 빠르게 풀 수 있는 문제가 바로 내가 쉽게 풀 수 있는 문제이다 . 알고리즘 공부를 하면서 이런 문제를 자주 만난다면 내가 공부를 한 성과가 나타나고 있다는 증거가 아닐까?

일단 $q$는 순열이기 때문에 $1$부터 $n$까지 모든 수가 한번씩 등장해야 한다. 그리고 $s = 0$인 곡과 $s = 1$인 곡 두 경우를 생각해야 한다. 싫어요를 누른 곡보다 반드시 좋아요를 누른 곡의 순위가 항상 높아야 하기 때문이다. 싫어요를 누른 곡을 모으고, 좋아요를 누른 곡을 따로 모으면 두 배열이 등장한다. 그리고 각 배열을 서로 정렬을 한 후 싫어요를 누른 곡의 맨 앞에서 부터 순위 1을 부여해서 순서대로 순위를 부여하면 답이다. 편차의 절대값이 가장 작은 평점을 구해야 하기 때문에 가장 작은 값에 가장 작은 순위를 부여해야 편차가 작아진다는 사실은 당연할 것이다.

그리고 모든 싫어요 곡에 순위를 부여하고 남은 순위에 아까랑 같은 방식으로 좋아요를 누른 곡에 순위를 차례로 매기면 답이다.

이때 정렬하기 전에 있는 위치에 순위를 부여해야 하기 때문에 곡을 모을때 곡의 순위와 더불어 곡의 index또한 같이 저장해야 하고 순위를 기준으로 정렬해야 한다.

정답 코드

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

using pii = pair<int, int>;

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<pii> zero, one;

        int a[n];
        for(auto& x : a) cin >> x;
        string s; cin >> s;
        for(int i = 0; i < n; i++){
            if(s[i] == '1') one.push_back({a[i], i});
            else zero.push_back({a[i], i});
        }

        sort(one.begin(), one.end());
        sort(zero.begin(), zero.end());
        int cnt = 1;

        for(auto [x, y] : zero) a[y] = cnt++;
        for(auto [x, y] : one) a[y] = cnt++;
        for(auto x : a) cout << x << " ";
        cout << "\n";
    }
    return 0;
}