Codeforces Round #793 (Div. 2) 1565 → 1545

https://codeforces.com/contest/1679

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

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

 

A. Palindromic Indices

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

Problem - A - Codeforces

문제

 

팰린드롬인 string s가 주어진다. 각 인덱스 i에 대해서 s[i]를 지워도 팰린드롬인 i의 개수를 출력하는 문제

 

풀이

 

가운데서부터 왼쪽 오른쪽으로 가운데와 같은 글자의 개수를 세주면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    int n;
    string s;
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            cin >> n >> s;
            int l = n / 2, r = n / 2;
            int ans = 0;
            if (n % 2) {
                ans++;
                l--; r++;
            }
            else{
                ans += 2;
                l--;
                l--;
                r++;
            }
            while (l >= 0) {
                if (s[l] == s[l + 1] && s[r] == s[r - 1])ans += 2;
                else break;
                l--; r++;
            }
            cout << ans << '\n';
            
        }
    }

 

B. AND Sorting

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

Problem - B - Codeforces

문제

 

n 길이의 permutation이 주어진다. 각 원소는 0 ~ n-1 로 이루어져있으며 a[i]&a[j]에 대해서 x가 나오면 두 위치를 swap할 수 있고 모든 swap후에 sort된 상태면 x-sortable하다고 한다. 여기서 가장 작은 x를 구하는 문제

 

풀이

 

AND 연산은 많이 할수록 작아지니 정렬이 안된 모든 원소를 AND 시킨 값을 출력해주면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    int a[200001];
    int pow2[31];
    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 < 28; i++)pow2[i] = 0;
            int n;
            cin >> n;
            for (int i = 0; i < n; i++) {
                cin >> a[i];
            }
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (a[i] != i) {
                    cnt++;
                    int start = 0;
                    while (a[i]) {
                        if (a[i] % 2)pow2[start]++;
                        a[i] /= 2;
                        start++;
                    }
                }
            }
            if (cnt == 0) {
                cout << 0 << '\n';
                continue;
            }
            int ans = 0;
            int start = 1;
            for (int i = 0; i < 28; i++) {
                if (pow2[i] == cnt)ans += (1 << i);
            }
            cout << ans << '\n';
     
            
        }
    }

C. LIS or Reverse LIS?

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

Problem - C - Codeforces

문제

 

n길이의 배열 a가 주어진다. a를 임의로 재배치해서 구한 LIS 값을 LIS1 이라고 하고 , reverse해서 LIS를 구한 값을 LIS2라고 했을떄 min(LIS1,LIS2)의 max값을 구하는 문제

 

풀이

 

배치 하는 방법은 배제하고 서로 다른 숫자의 수 + 같은숫자가 2개이상인 숫자의 수를 더해서 2로 나누어주고 나머지가 있다면 1을 증가시켜주면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;
map<int, int> Map;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        Map.clear();
        int n;
        cin >> n;
        int cnt1 = 0,cnt2=0;
        for (int i = 0; i < n; i++) {
            int t;
            cin >> t;
            Map[t]++;
            if (Map[t] == 1)cnt1++;
            if (Map[t] == 2)cnt2++;
        }
        int cnt = cnt1 + cnt2;
        int ans = cnt / 2;
        if (cnt % 2)ans++;
        cout << ans << '\n';
 
    }

 

 

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

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