Codeforces Round #754 (Div. 2) 1567 -> 1572

Dashboard - Codeforces Round #754 (Div. 2) - Codeforces

Dashboard - Codeforces Round #754 (Div. 2) - Codeforces

 !!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!

 

 

A. A.M. Deviation

Problem - A - Codeforces

Problem - A - Codeforces

문제

 

수 3개가 주어졌을 때 두 수를 골라 하나에 +1, 하나에 -1을 할 수 있다. 원하는 만큼 이 동작을 할 수 있을때 

abs(a1 + a3 - 2*a2)가 가장 작은 값을 출력하는 문제

 

풀이

 

a1+a3와 2*a2의 차이에서 3으로 나눈 나머지가 있을때는 1, 이외에는 0으로 출력한다.

 

 

코드

 

#include <bits/stdc++.h>
using namespace std;
long long a[3];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        for (int i = 0; i < 3; i++)cin >> a[i];
        long long dif = abs(a[0] + a[2] - 2 * a[1]);
        if (dif % 3)cout << 1 << '\n';
        else cout << 0 << '\n';
    }
}

 

 

B. Reverse Sort

Problem - B - Codeforces

Problem - B - Codeforces

 

문제

 

0과 1로 이루어진 스트링이 주어지고 비 오름차순으로 되어 있는 부분 수열을 골라 reverse하는 동작의 횟수를 최소로 하여 비 내림차순 스트링을 만드는 동작의 최소 횟수와 인덱스를 출력하는 문제

 

풀이

 

정렬하여 정렬한 스트링과 값이 다른 위치만 담아서 reverse 시켜주면 한번에 된다. 

 

코드

 

#include <bits/stdc++.h>
using namespace std;
vector<int> ans;
string s,s2;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        cin >> s;
        bool flag = true;
        for (int i = 1; i < n; i++) {
            if (s[i] < s[i - 1]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            cout << 0 << '\n';
            continue;
        }
        ans.clear();
        s2 = s;
        sort(s2.begin(), s2.end());
        cout << 1 << '\n';
        for (int i = 0; i < n; i++) {
            if (s[i] != s2[i])ans.push_back(i+1);
        }
        cout << ans.size() << ' ';
        for (auto kk : ans)cout << kk << ' ';
        cout << '\n';
    }
}

C. Dominant Character

Problem - C - Codeforces

Problem - C - Codeforces

 

 

문제

 

a, b, c로만 이루어진 스트링이 있다. 이 때 cnt(a) > cnt(b) && cnt(a) > cnt(c) 인 최소 부분 스트링의 길이를 찾아 출력하는 문제

 

풀이

 

답은 aXa , aXXa , aXXaXXa중에 하나만 있고 이외에는 아무리 길어져도 답이 성립할 수 없으므로 최대길이 7까지만 브루트포스로 서치 해본다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
int cnt[1000001][3];
string s;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n >> s;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                cnt[i][j] = 0;
            }
        }
        cnt[0][s[0] - 'a']++;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                cnt[i][j] += cnt[i - 1][j];
            }
            cnt[i][s[i] - 'a']++;
        }
 
        int ans = -1;
        for (int l = 1; l <= 10; l++) {
            for (int i = 0; i < n; i++) {
                int start = i, end = i + l;
                if (end >= n)break;
                int cnta = cnt[end][0],cntb=cnt[end][1],cntc=cnt[end][2];
                if (start != 0) {
                    cnta -= cnt[start - 1][0];
                    cntb -= cnt[start - 1][1];
                    cntc -= cnt[start - 1][2];
                }
                if (cnta > cntb && cnta > cntc) {
                    ans = l + 1;
                    break;
                }
            }
            if (ans != -1)break;
        }
        cout << ans << '\n';
    }
}

 

 

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.