Codeforces Round #803 (Div. 2) 1665 → 1693

https://codeforces.com/contest/1698

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

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

 

A. XOR Mixup

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

Problem - A - Codeforces

문제

n이 주어진다. 이후 n-1개의 원소와 모든 원소를 xor한 값이 주어진다. 나머지 한개의 원소를 출력하는 문제

 

풀이

 

아무 원소나 출력하면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    int a[130];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            int ans = 0;
            int n;
            cin >> n;
            for (int i = 0; i < n; i++) {
                cin >> a[i];
            }
            cout << a[0] << '\n';
            
        }
     
    }

 

B. Rising Sand

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

Problem - B - Codeforces

문제

 

n과 k가 주어진다. n길이의 배열이 주어지고 아래와 같은 operation을 원하는만큼 할수 있을 때 a[i-1] + a[i+1] < a[i] 를 만족하는 원소의 최대 개수를 출력하는 문제

 

풀이

 

k가 1이라면 답은 ceil((n-1)/2)이 된다. 아니라면 어떠한 연산으로도 답의 개수를 증가시킬 수 없으므로 원 배열의 답을 출력한다.

 

코드

 

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

C. 3SUM Closure

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

Problem - C - Codeforces

문제

 

n길이의 배열 a가 주어진다. 가능한 모든 i<j<k인 인덱스 3개를 골라 a[i]+a[j]+a[k]가 배열 안에 들어 있다면 YES를 아니라면 NO를 출력하는 문제

 

풀이

 

가장 작은 원소 3개와 가장 큰 원소 3개로 이룰 수 있는 경우의 수에 대하여 모두 확인해준다.

 

코드

    #include <bits/stdc++.h>
    using namespace std;
    long long a[200001];
    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 = 1; i <= n; i++) {
                cin >> a[i];
            }
            if (n == 3) {
                long long sum = a[1] + a[2] + a[3];
                bool flag = false;
                for (int i = 1; i <= 3; i++) {
                    if (sum == a[i])flag = true;
                }
                if (flag)cout << "YES\n";
                else cout << "NO\n";
                continue;
            }
            sort(a + 1, a + 1 + n);
            vector<long long> v;
            v.push_back(a[1] + a[2] + a[3]);
            v.push_back(a[1] + a[2] + a[n - 1]);
            v.push_back(a[1] + a[2] + a[n]);
            v.push_back(a[1] + a[n - 1] + a[n]);
            v.push_back(a[2] + a[n - 1] + a[n]);
            v.push_back(a[n - 2] + a[n - 1] + a[n]);
            bool flag = true;
            for (int i = 0; i < 6; i++) {
                bool tflag = false;
                for (int j = 1; j <= n; j++) {
                    if (v[i] == a[j]) {
                        tflag = true;
                        break;
                    }
                }
                if (tflag == false)flag = false;
            }
            if (flag) cout << "YES\n";
            else cout << "NO\n";
        }
     
    }

 

D. Fixed Point Guessing

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

Problem - D - Codeforces

문제

 

n이 주어지고 최초에 n길이의 permutation이 있다. n은 홀수이고 (n-1)/2 개의 쌍을 골라 각 원소를 swap한다. swap이 안된 나머지 1개의 원소를 찾아야 하며 쿼리를 최대 15번 줄 수 있고 1개의 쿼리에 l..r을 보내 l..r의 오름차순 정렬한 원소들을 쿼리의 답으로 받아서 찾는 문제.

 

풀이

 

짝수 길이의 l..r을 보내고 만약 swap안된 원소가 있다면  l..r 구간 안에 l,r 사이값을 가지는 원소의 개수가 홀수개가 되고 아니라면 짝수개가 된다. 이 관찰 결과를 통해 이분탐색을 해주면 된다.

 

 

코드

    #include <bits/stdc++.h>
    using namespace std;
    string ans = "";
    int a[10001];
    int main() {
        ios_base::sync_with_stdio(false);
        int T;
        cin >> T;
        while (T--) {
            int n;
            cin >> n;
            if (n <= 15) {
                int ans = -1;
                int num;
                for (int i = 1; i <= n; i++) {
                    cout << "? " << i << ' ' << i << endl;
                    cin >> num;
                    if (i == num) {
                        ans = i;
                        break;
                    }
                }
                cout << "! "<<ans << endl;
                continue;
            }
            //짝수개를 쏠때 홀수개의 맞는 범위가 나온다
            int l = 1, r = n,ans=-1;
            while (l < r) {
                if ((l + 1) == r) {
                    int num;
                    cout << "? " << l << ' ' << l << endl;
                    cin >> num;
                    if (num == l)ans = l;
                    else ans = r;
                    break;
                }
                int mid = (l + r) / 2;
                if ((mid - l + 1) % 2)mid--;
                
                cout << "? " << l << ' ' << mid << endl;
                int cnt = 0;
                for (int i = l; i <= mid; i++) {
                    int t;
                    cin >> t;
                    if (t >= l && t <= mid)cnt++;
                }
                if (cnt % 2)r = mid;
                else l = mid + 1;
            }
            if (l == r)cout << "! " << l << endl;
            else cout << "! " << ans << endl;
     
        }
     
    }

 

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

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