Codeforces Round #767 (Div. 2) 1673 -> 1689

https://codeforces.com/contest/1629

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

 

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

 

A. Download More RAM

https://codeforces.com/contest/1629/problem/A

Problem - A - Codeforces

문제

 

n개의 서로 다른 메모리를 증가시킬 소프트웨어가 주어진다. 실행시킬때 a[i] 메모리가 필요하며, 이후에는 돌아온다. 실행 시킨 후 b[i]메모리를 영구적으로 얻는다. 처음에 k의 메모리가 있을 때,가능한 메모리의 최대 값을 출력하는 문제

 

풀이

 

pair 쌍으로 받고 , a[i] 순으로 오름차순 정렬하여 가장 싼 메모리가 필요한 소프트웨어부터 확실하게 b[i]를 k에 추가시킨 후 출력한다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    pair<long long, long long> p[101];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            long long n, k;
            cin >> n >> k;
            for (int i = 0; i < n; i++) {
                cin >> p[i].first;
            }
     
            for (int i = 0; i < n; i++) {
                cin >> p[i].second;
            }
            sort(p, p + n);
     
            for (int i = 0; i < n; i++) {
                if (p[i].first <= k) {
                    k += p[i].second;
                }
                else break;
            }
            cout << k << '\n';
        }
     
    }

 

 

B. GCD Arrays

https://codeforces.com/contest/1629/problem/B

Problem - B - Codeforces

 

문제

 

l,r,k를 입력으로준다. l부터 r까지의 정수 배열이 있는데 이 배열의 원소들중 두개의 정수를 골라 곱하여 배열의 맨뒤에 추가하는 연산을 최대 k번 할 수 있을 때 모든 배열 원소의 gcd를 2이상 만들 수 있으면 YES 그렇지 않다면 NO를 출력하는 문제

 

풀이

 

l과r사이의 모든 홀수를 곱하고 , 아무 짝수와 한번 곱하면 모든 원소의 gcd가 2가 된다. 이 방법이 최소의 숫자이며 결국 l과r사이의 홀수 >k 라면 NO 이외에는 YES를 출력해주면 된다.이 때 1을 제외한 l==r은 무조건 YES로 예외 처리를 해준다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
     
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            long long l, r,k;
            cin >> l >> r>>k;
            if (l == r) {
                if (l == 1)cout << "NO\n";
                else cout << "YES\n";
                continue;
            }
            long long cnt1 = (l-1) / 2;
            if ((l-1) % 2)cnt1++;
            long long cnt2 = r / 2;
            if (r % 2)cnt2++;
            cnt2 -= cnt1;
            if (cnt2 > k)cout << "NO\n";
            else cout << "YES\n";
        }
     
    }

C. Meximum Array

https://codeforces.com/contest/1629/problem/C

Problem - C - Codeforces

문제

 

a 배열과 b배열이 있다. b배열은 처음에 비었고, a배열은 입력으로 주어진다. 이때 k 를 골라 (1~|a|) a배열의 앞에서부터 k번째 배열까지의 MEX값을 b배열의 맨 뒤에 추가로 삽입한다. a배열이 없어질 때 까지 이 과정을 반복해서 b배열이 사전적으로 MAX값을 가졌을 때 b를 출력하는 문제

 

풀이

 

각 숫자마다 vector에 인덱스를 넣은 후 내림차순으로 정렬하여 사용한다. 만약 이전에 d라는 인덱스까지 사용했다면 d이하의 인덱스는 vector에서 빼주면서 해당 숫자가 없게되면 그숫자를 MEX로 b에 삽입해준다. 다만 { 2 2 2 2 } 배열처럼 특정 숫자가 계속 없을 때는 d=max(d+1,최대 인덱스)로 값을 갱신해주면서 나머지 수들을 메꾸어주면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    int a[200001];
    vector<int> v[200001], ans;
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            int n;
            cin >> n;
            for (int i = 0; i <= n; i++)v[i].clear();
            ans.clear();
            for (int i = 1; i <= n; i++) {
                cin >> a[i];
                v[a[i]].push_back(i);
            }
            for (int i = 0; i <= n; i++) {
                sort(v[i].begin(), v[i].end(), greater<int>());
                //for (auto kk : v[i])cout << kk << ' ';
                //cout << '\n';
            }
            int d = 0;
            while (true) {
                if (d >= n)break;
                int MAX = 0,lasti=0;
                for (int i = 0; i <= n; i++) {
                    while (!v[i].empty()) {
                        if (v[i].back() <= d)v[i].pop_back();
                        else break;
                    }
                    if (v[i].empty()) {
                        break;
                    }
                    MAX = max(v[i].back(), MAX);
                    lasti = i + 1;
                    v[i].pop_back();
                }
                ans.push_back(lasti);
                d = max(MAX,d+1);
            }
            cout << ans.size() << '\n';
            for (auto kk : ans)cout << kk << ' ';
            cout << '\n';
        }
     
    }

 

D. Peculiar Movie Preferences

https://codeforces.com/contest/1629/problem/D

Problem - D - Codeforces

문제

 

n개의 최대 길이가 3인 string이 주어진다. 이 문자열 집합의 부분집합중에서 팰린드롬을 맞출 수 있으면 YES를 아니라면 NO를 출력하는 문제

 

풀이

 

길이가 1이거나 시작부터 팰린드롬인 문자열들이 있다면 답은 YES이고, 나머지는 2글자와 3글자들을 map에 저장하여 log(n)시간복잡도로 찾으면 된다. 다만 2+3 글자와 3+2 글자로도 팰린드롬이 될 수있으니 이것 까지 map으로 확인해주면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    string s[100001];
    map<string, bool> Map2, Map3,Map32;
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            int n;
            cin >> n;
            Map2.clear(); Map3.clear(); Map32.clear();
            bool flag = false;
            for (int i = 0; i < n; i++) {
                cin >> s[i];
                bool tflag = false;
                if (s[i].size() == 1) {
                    tflag = true;
                }
                else if (s[i].size() == 2) {
                    string re = "";
                    re += s[i][1]; re += s[i][0];
                    if (Map2[re] || Map32[re])tflag = true;
                    //추가
                    Map2[s[i]] = true;
                    if (s[i][0] == s[i][1]) {
                        tflag = true;
                    }
                }
                else {
                    string re = "";
                    re += s[i][2]; re += s[i][1]; re += s[i][0];
                    if (Map3[re])tflag = true;
                    re = "";
                    re += s[i][2]; re += s[i][1];
                    if (Map2[re])tflag = true;
                    //추가
                    Map3[s[i]] = true;
                    string temp = "";
                    temp += s[i][0]; temp += s[i][1];
                    Map32[temp] = true;
                    if (s[i][0] == s[i][2]) {
                        tflag = true;
                    }
                }
                if (tflag)flag = true;
            }
            if (flag) {
                cout << "YES\n";
            }
            else cout << "NO\n";
            //for (int i = 0; i < n; i++) {
            //    if (s[i].size() == 1) {
     
            //    }
            //    else if (s[i].size() == 2) {
     
            //    }
            //    else {
     
            //    }
            //}
        }
     
    }

 

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

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