Codeforces Round #785 (Div. 2) 1634 → 1681

https://codeforces.com/contest/1673

https://codeforces.com/contest/1673

!!!! 모든 답은 제 풀이일 뿐 공부를 위한 올바른 정해가 아닐 수 있습니다 !!!!

 

A. Subtle Substring Subtraction

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

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

문제

 

string s가 주어진다. 앨리스와 밥은 게임을 하는데 앨리스는 자기의 턴에 짝수 길이의 연속된 substring을 제거할 수 있고 밥은 자기 턴에 홀수 길이의 연속된 substring을 제거할 수 있다. 제거한 substring의 점수는 'a' = 1, 'b' = 2 ..등의 합산이며 둘다 최선으로 플레이 했을때 승자와 점수 차이를 출력하는 문제. 턴은 앨리스 먼저 시작한다.

 

풀이

 

s길이가 짝수라면 승자는 앨리스와 전체 string의 점수 합이고 홀수라면 왼쪽끝이나 오른쪽끝의 최소 값을 밥에게 주어 점수계산을 해주면 된다.

 

코드

 

    #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--) {
            string s;
            cin >> s;
            int sum = 0;
            for (int i = 0; i < s.size(); i++) {
                sum += (s[i] - 'a' + 1);
            }
            int MIN = min(s[0] - 'a' + 1, s.back() - 'a' + 1);
            if (s.size() == 1) {
                cout << "Bob " << MIN << '\n';
            }
            else {
                if (s.size() % 2) cout << "Alice " << sum - MIN * 2 << '\n';
                else cout << "Alice " << sum << '\n';
            }
        }
    }

 

B. A Perfectly Balanced String?

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

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

 

문제

 

string s가 준다. triplets (t,u,v) 함수가 있는데 t는 s의 연속된 substring이고 u와 v는 s에 등장하는 character이다. u와 v의 t에서 u와 v의 개수 차이를 triplets의 결과 값이라고 했을때 모든 substring의 triplets값이 1이하라면 Perfectly Balanced라고 불린다. 주어진 s가 Perfectly Balanced 함수인지 아닌지 판별하는 문제

 

풀이

 

각 2개의 같은 character들의 인덱스를 저장하여 이들을 포함한 사이 string을 t로 두고 안에 하나라도 u나 v의 개수가 0인게 있다면 답은 YES 아니라면 NO를 출력하는 문제

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    string s;
    int cnt[200010][130];
    vector<int> v[130];
    bool check[130];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
     
        while (T--) {
            for (int i = 'a'; i <= 'z'; i++) {
                v[i].clear();
                check[i] = false;
            }
            cin >> s;
            int n = s.size();
            s = " " + s;
            bool flag = true;
            int num = 0;
            for (int i = 1; i <= n; i++) {
                if (s[i] == s[1])num++;
                check[s[i]] = true;
                
            }
            if (num == n) {
                cout << "YES\n";
                continue;
            }
            for (int i = 1; i < n; i++) {
                if (s[i] == s[i + 1]) {
                    flag = false;
                    break;
                }
            }
     
            if (flag == false) {
                cout << "NO\n";
                continue;
            }
            for (int i = 1; i <= n; i++) {
                v[s[i]].push_back(i);
                for (int j = 'a'; j <= 'z'; j++) {
                    cnt[i][j] = cnt[i - 1][j];
                }
                cnt[i][s[i]]++;
            }
            
            for (int i = 'a'; i <= 'z'; i++) {
                for (int j = 1; j < v[i].size(); j++) {
                    int l = v[i][j - 1] - 1, r = v[i][j];
                    for (int k = 'a'; k <= 'z'; k++) {
                        if (check[k] == false)continue;
                        int tnum = cnt[r][k] - cnt[l][k];
                        if (tnum == 0) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag == false)break;
                }
                if (flag == false)break;
            }
            if (flag)cout << "YES\n";
            else cout << "NO\n";
        }
    }

C. Palindrome Basis

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

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

문제

 

숫자 n이 주어진다. n을 각 팰린드롬 수의 합으로 표현할 수 있는 경우의 수를 출력하는 문제 이 때 1+1+3 과 1+3+1 과 같은 순서만 다른 숫자의 합은 같은 경우의 수로 가정한다.

 

 

풀이

 

팰린드롬 수를 따로 찾아내고 백준의 동전2 dp와 똑같이 점화식을 세어 풀어주면 된다.

 

코드

    #include <bits/stdc++.h>
    using namespace std;
    long long mod = 1000000007;
    long long d[40001];
    vector<int> v;
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        for (int i = 1; i < 40001; i++) {
            bool flag = true;
            string s = to_string(i);
            int l = 0, r = s.size() - 1;
            while (l < r) {
                if (s[l] != s[r]) {
                    flag = false;
                    break;
                }
                l++; r--;
            }
            if (flag)v.push_back(i);
        }
        d[0] = 1;
        for (int i = 0; i < v.size(); i++) {
            for (int j = v[i]; j < 40001; j++) {
                d[j] += d[j - v[i]];
                d[j] %= mod;
            }
        }
        int T;
        cin >> T;
     
        while (T--) {
            int n;
            cin >> n;
            cout << d[n]%mod << '\n';
        }
    }

 

 

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

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