Codeforces Round #764 A부터 D까지 업솔빙

Codeforces Round #764 A부터 D까지 업솔빙

C번 문제까지는 어찌 문제를 풀었는데, 퍼포먼스는 1100정도 나온 것 같다. d번 문제는 이분탐색이라는 단서가 너무 많이 주어져 있었는데, 활용능력하고 결정함수를 만드는 능력이 떨어져서 못푼것 같다.

A. Plus One on the Subset (*800)

접기/펼치기

문제 설명
배열 $a[1, ..., n]$이 주어진다. 그리고 다음 연산을 몇번이고 수행해서 배열의 모든 원소를 같게 만들고 싶다.

• 한 연산에서, 배열에 있는 index를 선택하고 해당 index에 속한 원소값을 1 올린다.

배열에 있는 모든 원소를 모두 같게 만들기 위해서 필요한 최소 연산횟수는 무엇인가?

문제 해설
index를 제한없이 선택할 수 있기 때문에 이 문제가 쉽다. 그냥 배열에서 가장 큰 원소에서 배열에서 가장 작은 원소의 차이만큼 연산을 수행하면 반드시 모든 원소를 같게 만들 수 있다. 왜냐하면 배열에서 가장 큰 원소는 해당 원소보다 작아질 수 없기 때문에 나머지 원소를 배열에서 가장 큰 원소에 맞추는 것이 최선이기 때문이다.

정답 코드

#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;
        sort(a, a + n);
        cout << (a[n - 1] - a[0]) << "\n";
    }
    return 0;
}

B. Make AP (*900)

접기/펼치기

문제 설명
$3$개 양의 정수 $a, b, c$가 주어진다. 그리고 다음 주어지는 연산을 한번만 수행할 수 있다.

• 양의 정수 $m$을 선택하고 $a, b, c$중 1개에만 $m$을 곱한다.

이 연산을 수행하고 나서 $a, b, c$ 이 순서대로 등차수열을 만들고 싶다. 반드시 $a, b, c$의 순서는 바꾸면 안된다.

등차수열을 만들 수 있다면 yes를, 만들 수 없다면 no를 출력한다.

문제 해설
$a$에 $m$을 , $b$에 $m$을, $c$에 $m$을 곱한 3가지 경우의 수를 모두 고려하면 된다. 등차수열인지 확인하는 가장 쉬운 방법은 등차중항 공식을 이용하는 것이고, $m$이 양의 정수라는 것을 이용해서 나머지 연산을 할 때 나머지가 $0$인지, $m$이 양수인지 조건을 모두 고려하면 된다.

정답 코드

#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;
        bool flag = false;
        if((2 * b - c) > 0 and (2 * b - c) % a == 0) flag = true;
        if((2 * b - a) > 0 and (2 * b - a) % c == 0) flag = true;
        if((a + c) % (2 * b) == 0) flag = true;
        cout << (flag ? "yes" : "no") << "\n";
    }
    return 0;
}

C. Division by Two and Permutation (*1100)

접기/펼치기

문제 설명
$n$개 양의 정수로 이루어진 배열 $a$가 주어진다. 다음 연산을 수행할 수 있다.

• 한 연산에서 $a_i$을 $[\frac{a_i}{2}]$ 로 바꿀 수 있다.

이 연산을 몇번이고 수행할 수 있다. 이 연산을 수행했을 때, $a$를 $1$부터 $n$까지의 순열로 만들수 있는지 결정하라.

문제 해설
이 문제를 보고 일단 그리디 알고리즘을 사용하는 문제라는 것을 알았다. $1$부터 $n$까지 숫자가 등장하는지 기록하는 배열 cnt를 준비한다. 그리고 먼저 $n$ 이하인 원소들은 굳이 연산을 진행할 필요가 없기 때문에 바로 cnt배열에 체크를 한다. $n$보다 큰 수는 $2$를 나누어서 $n$보다 작은 수를 찾아야 하는데, 이때 연산 결과로 나온 수가 이미 존재한다면 다시 연산을 진행한다. 이때 모든 연산을 진행하고 $0$이 될때까지 배열의 위치를 못찾았다면 해당 숫자로는 순열을 만들 수 없다고 판단할 수 있기 때문에 no를 출력한다. 그렇지 않고 모든 연산을 다 마쳤다면 yes를 출력한다.

정답 코드

#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], cnt[n + 1] = {0, };
        for(auto& x : a) cin >> x;
        bool flag = true;
        for(int i = 0; i < n; i++){
            int tmp = a[i];
            while(tmp and (tmp > n or cnt[tmp])) tmp >>= 1;
            if(!tmp) flag = false;
            cnt[tmp] = 1;
        }
        cout << (flag ? "yes" : "no") << "\n";
    }
    return 0;
}

D. Palindromes Coloring (*1400)

접기/펼치기

문제 설명
알파벳 소문자로 이루어진 문자열 $s$가 주어진다.
이 문자열에 있는 문자를 $1$부터 $k$까지 색깔로 칠할 수 있다. 모든 문자를 모두 색칠할 필요 없으며, $1$ 부터 $k$개 색깔로 반드시 1개 이상의 문자는 칠해야 한다.

그리고 같은 색깔로 칠한 문자끼리는 몇번이고 자리를 바꿀 수 있다.

그러면 $k$개 문자열이 생성되는데, $s$문자열에서 $i$번째 색깔로 칠한 문자로 이루어진 문자열이다.

우리가 할 일은 $k$개 문자열 모두가 펠린드롬인지 확인하는 것이다. 그리고 $k$개 문자열중 길이가 가장 작은게 가장 커야한다.

$k$개 펠린드롬 문자열중 가장 작은 문자열의 길이가 가장 큰 경우를 출력하라.

문제 해설
가장 작은경우 중 가장 큰 수를 찾아야 하는 문제는 반드시 이분탐색으로 풀 수 있는 문제이다. 즉 해당 길이가 $x$라고 할 때, $x = 0$인 경우는 반드시 만족하고, $x = n + 1$인 경우는 반드시 만족 할 수 없을 때, $TTTTTFFFFF$에서 맨 오른쪽에 있는 T를 구하면 되는 전형적인 이분탐색 문제이다.

그러면 우리는 해당 $x$만 구하면 된다. 여기서 $x$는 펠린드롬인 문자열 중에서 가장 작지만 가장 큰 수이다. 해당 문자열이 펠린드롬이려면 $x$가 홀수, 짝수인지에 따라서 나뉘어진다.

여기서 우리는 두 변수를 정의할 것이다. even은 문자열이 2개 나오는 횟수이다. 만약 $a$가 4번 나온다면 even = 2이다. 왜냐하면 문자열 $a$가 2번씩 2개 나왔기 때문이다. odd는 문자열이 1개만 나오는 횟수이다. 만약 $a$가 5개 나온다면 even = 2이고, odd = 1이다.

이렇게 변수를 정의하면

• x가 홀수 일때는, even이 $x / 2$개 필요하고, 나머지 한 문자를 odd로 채우면 된다. 거기에 이 문자열이 $k$개 나와야 하기때문에 $(x / 2) * k$개 even과 $k$개 odd가 필요하다. 이때 주의해야 할 점은 $even$을 쓰고 남은 문자를 odd에 포함시켜서 사용할 수 있다는 점이다. 1 even == 2odd이기 때문에 숫자 변환에 주의해야 한다.
• x가 짝수일 때는 evene이 $x / 2$개만 있으면 되고, odd는 고려할 필요 없다.

위 결정조건을 만족하는 경우가 있으면 $l = mid$하고, 만족하지 않는다면 $r = mid$를 해서 이분탐색을 진행한다. 이 문제는 변수 정의하는 것과 결정함수 정하는 것이 중요했던 문제이다.

정답 코드

#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 n, k; cin >> n >> k;
        string s; cin >> s;
        ll even = 0, odd = 0, cnt[26] = {0, };
        for(auto c : s) cnt[c - 'a']++;
        for(auto x : cnt){
            even += x / 2;
            odd += x % 2;
        }

        ll l = 0, r = 200010;
        while(l + 1 < r){
            ll mid = (l + r) >> 1;
            bool flag = true;
            if(mid & 1){
                ll need = (mid / 2) * k;
                if(need > even) flag = false;
                else{
                    flag = (odd + 2 * (even - need) < k ? false : true);
                }
            }else flag = ((mid / 2) * k > even ? false : true);

            (flag ? l : r) = mid;
        }
        cout << l << "\n";
    }
    return 0;
}