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

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

A번문제만 푼 대회 B번 문제는 계속 봐도 해설이 안떠올라서 그나마 만만해 보이는 C번 문제로 넘어갔는데 경우의수 1가지를 못찾아서 못풀었다. *1400난이도 치고는 경우의수 7가지만 찾으면 되는 쉬운 문제 였는데, 못풀어서 아쉬웠다. B번 문제는 이전에 풀었던 C. Rings 랑 비슷한 문제라서 더더욱 폿풀어서 아쉬운 문제였다. 계속 훈련을 하면 언젠가는 단단해 지겠지..
이번 대회에서 배운 것은

1. 문제에서 제공하는 예제 풀이에 너무 몰입하여 생각하지 않기.
2. A, B, C는 생각보다 쉬운 문제다!
3. 끝까지 경우의수 생각하면서 풀기

A. A.M. Deviation (*800)

접기/펼치기

문제 설명
세 숫자 $a_1, a_2, a_3$ 의 산술평균은 다음과 같이 정의한다.

• $d(a_1, a_2, a_3) = |a_1 + a_3 - 2 \cdot a_2|$

우리가 구해야 할것은 $d(a_1, a_2, a_3)$의 값을 최소화 하는 것이다. 이 값을 최소화하기 위해서 우리는 다음 연산을 몇번이고 수행할 수 있다. (수행하지 않을 수도 있다.)

• ${1, 2, 3}$ 에서 $i \neq j$ 를 만족하는 $i, j$를 선택하고 $a_i$ 값을 1 증가시키고 $a_j$값을 1 감소시킨다.

위에서 말한 연산을 몇번이고 수행해서 $d(a_1, a_2, a_3)$ 의 최솟값을 구하자.

문제 해설
일단 $a_1, a_3$의 값을 각각 1씩 늘리고 1씩 줄이면 값이 변하지 않는다. 따라서 $a_2$ 값을 1 줄이거나 반드시 1 늘려야 한다. 그렇다면 $|a_1 + a_3 - 2 \cdot a_2 - 3\alpha|$ 식이 나온다. $\alpha$ 값은 정수이다.

반드시 원래 값에서 3씩 더해지거나 빼지기 때문에 다음 성질이 성립한다.

• 일단 $a_1 + a_3 - 2 \cdot a_2$ 값이 3으로 나누어 떨어진다면 저 값은 반드시 0이 된다.
• $a_1 + a_3 - 2 \cdot a_2$ 값이 3으로 나누어 떨어지지 않는다면 $3\alpha$를 더하거나 빼서 절댓값이 1이 되게 만들 수 있다. 만약 저 값이 $5$라면 이 수에서 $-6$을 더해서 $|-1| = 1$을 만들 수 있고, 저 값이 $4$라면 이 수에서 $-3$을 더해서 $1$을 만들 수 있다.

따라서 $a_1 + a_3 - 2 \cdot a_2$이 값이 3으로 나누어 떨어진다면 답은 0, 아니면 답은 1이다.

정답 코드

#include <iostream>
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;
        cout << ((a + c - 2 * b) % 3 ? 1 : 0) << "\n";
    }
    return 0;
}

B. Reverse Sort (*1000)

접기/펼치기

문제 설명
길이가 $n$인 이진수 문자열 $s$를 오름차순으로 정렬하고 싶다. 정렬을 할 때 다음 연산을 사용할 수 있다.

1. $1 \le k \le n$ 인 $k$를 선택하고 $1 \le i_1 < i_2 < ... < i_k \le n$ 인 index를 가지고 있는 문자 $s_{i_1} \ge s_{i_2} \ge ... \ge s_{i_k}$ 를 선택한다.
2. 이 문자들을 모두 뒤집고 원래 위치에 뒤집은 문자열을 넣는다.

오름차순이 아닌 문자열을 오름차순으로 정렬하기 위해서 필요한 최소 연산의 횟수를 찾아라.

문제 해설
대회에서는 어떻게 풀지?라고 생각하면서 Note나 Example처럼 해보면서 문제를 풀 방법을 고민하고 있었다. 내가 이 대회에서 배운 점에서 적어놓은 것 처럼 문제에서 제공하는 예제풀이에 너무 맹목적으로 생각하면 안된다는 것을 다시한번 상기시켜준 문제인 것 같다. 예제풀이대로 풀면 어짜피 정해가 아니기 때문에 풀이가 산으로 간다. ㅋㅋㅋㅋㅋㅋ

일단 이미 정렬되어 있는 경우는 연산이 필요가 없으므로 0을 출력해 주면 된다. 정렬이 되어 있는지 어떻게 판단을 할까? c++ STL에서는 이럴때 필요한 함수를 미리 구현해 두었다. algorithm 헤더에 있는 is_sorted()함수를 사용하면 쉽게 정렬이 되어 있는지 판단할 수 있다.

정렬이 안되어 있는 경우는 어떻게 할까? 결론부터 말하자면 반드시 연산 1번으로 오름차순으로 정렬할 수 있다. 원래 정렬이 안되어 있는 문자열을 $10100$이라고 하면 정렬이 되어있는 문자열은 $00011$이다. 그렇다면 정렬이 되어있는 문자열과 정렬이 되어있지 않은 문자열을 비교해서 정렬이 되어있는 문자열의 각 문자 위치에 있으면 안되는 문자를 모두 선택해서 뒤집으면 정렬이 된다.

1이 원래 정렬된 상태에서 있어야하는 위치는 $1$의 개수를 cnt라고 하면 $n - cnt + 1$부터 $n$까지이다. 그렇다면 0이 원래 정렬된 상태에 있어야 하는 위치는 $1$ 부터 $n - cnt$까지일 것이다. 각각 범위를 순회하면서 정렬된 문자열 기준으로 $1$이 있어야하는 위치에 $0$이 있는 경우, $0$이 있어야 하는 위치에 $1$이 있어야 하는 경우의 index를 모두 긁어모아서 출력하면 답이다.

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
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;
        char s[n];
        int cnt = 0;
        for(int i = 0; i < n; i++){
            cin >> s[i];
            if(s[i] == '1') cnt++;
        }
        if(is_sorted(s, s + n)){
            cout << 0 << "\n";
            continue;
        }

        vector<int> v;
        for(int i = 0; i < n - cnt; i++){
            if(s[i] != '0') v.push_back(i + 1);
        }

        for(int i = n - cnt; i < n; i++){
            if(s[i] != '1') v.push_back(i + 1);
        }

        cout << 1 << "\n" << v.size() << " ";
        for(auto x : v) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

C. Dominant Character (*1400)

접기/펼치기

문제 설명
문자 a, b, c로만 이루어진 길이가 $n$인 문자열 $s$가 있다.

다음 조건을 모두 만족하는 가장 작은 길이의 substring을 찾고 싶다.

• substring의 길이는 최소 2이상이다.
• substring에서 a의 개수는 c의 개수보다 커야한다.
• substring에서 a의 개수는 b의 개수보다 커야한다.

가장 작은 길이의 substring을 찾게 도와주자.

문제 해설
따지고보면 B번보다 쉬운 문제라고 생각한다. 단순히 문제의 조건을 만족하는 문자열의 경우의 수를 세보면 총 7가지 문자열 밖에 없다는 것을 알 수 있고, 찾기 어려운 경우는 $abbacca, accabba$이다. 이거 찾으면 문제는 그냥 쉽다. 길이가 작은 순으로 조건을 모두 만족시키는 문자열을 배열에 넣고 반복문을 돌려서 먼저 찾은 순서대로 답을 출력하고 끝내면 된다. 만약 저 7가지 경우가 아닌 경우 조건을 만족하는 substring은 반드시 존재하지 않기 때문에 -1을 출력하면 된다.

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    string a[7] = {"aa", "aba", "aca", "abca", "acba", "abbacca", "accabba"};
    while(t--){
        int n; cin >> n;
        string s; cin >> s;
        int ans = -1;
        for(int i = 0; i < 7; i++){
            if(s.find(a[i]) != -1){
                ans = a[i].length();
                break;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}