Codeforces Round #776 (Div. 3) 1491 -> 1545

https://codeforces.com/contest/1650

Dashboard - Codeforces Round #776 (Div. 3) - Codeforces

 

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

 

A. Deletions of Two Adjacent Letters

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

Problem - A - Codeforces

 

문제

 

홀수길이의 string 과 1개의 character가 입력으로 주어진다. 입력받은 string의 character를 2개씩 지워 입력받은 character로 만들 수 있으면 YES 아니면 NO를 출력하는 문제

 

풀이

 

각 스트링의 홀수번째 자리에 하나라도 character가 있으면 YES 아니면 NO를 출력하면 된다.

 

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    string s1, s2;
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            cin >> s1 >> s2;
            bool flag = false;
            for (int i = 0; i < s1.size(); i+=2) {
                if (s1[i] == s2[0]) {
                    flag = true;
                    break;
                }
            }
            if (flag)cout << "YES\n";
            else cout << "NO\n";
        }
     
    }

 

B. DIV + MOD

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

Problem - B - Codeforces

 

문제

 

fa(x)를 x/a + x%a 라고 했을 때 l , r , a를 입력받아 l과 r사이의 x값 중 fa(x) 최대값을 구하는 문제

 

풀이

 

우선 r < x라면 r이 최대값이니 그대로 r 출력하고 이외에는 l과 r을 a로 나눈후 나눈 나눈 몫이 같으면 r을 출력 아니라면 r과 ,  (r을 나눈 몫 -1) + (a-1)의 값을 비교해서 출력해주면 된다.

 

코드

 

    #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, a;
            cin >> l >> r >> a;
            if (r < a) {
                cout << r / a + r << '\n';
            }
            else {
                long long div1 = l / a, div2 = r / a;
                if (div1 == div2) {
                    cout << r / a + r % a << '\n';
                }
                else {
                    cout << max(div2 + r % a, div2 - 1 + (a - 1LL)) << '\n';
                }
            }
        }
     
    }

 

C. Weight of the System of Nested Segments

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

Problem - C - Codeforces

 

문제

 

1개의 직선에 1~m까지 m개의 점이 있다. 각 점은 x[i]위치에 있고 w[i]의 가중치를 가지고 있다. n이 주어지며 n개의 각 점 쌍을 연결시키는데 서로의 쌍들이 다른 쌍과 비교해서 완전히 내부에 있거나 완전히 외부에 있어야 한다. 이때 만들 수 있는 점들의 가중치의 최소 값을 출력하는 문제

 

풀이

 

n*2개를 제외한 나머지점들은 가중치가 가장 큰 순서대로 빼고 남은 것들끼리 조건에 맞게 연결시켜주면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    struct POS {
        long long x, w,idx;
        bool operator<(const POS& p)const {
            return w > p.w;
        }
    };
    bool cmp(POS a, POS b) {
        return a.x < b.x;
    }
    POS p[200001];
    vector<POS> v;
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            v.clear();
            int n, m;
            cin >> n >> m;
            for (int i = 0; i < m; i++) {
                cin >> p[i].x >> p[i].w;
                p[i].idx = i+1;
            }
            sort(p, p + m);
            int dif = m - n * 2;
            long long ans = 0;
            for (int i = dif; i < m; i++) {
                v.push_back(p[i]);
                ans += p[i].w;
            }
            sort(v.begin(), v.end(), cmp);
            cout << ans << '\n';
            for (int i = 0; i < n; i++) {
                cout << v[i].idx << ' ' << v[v.size() - i - 1].idx << '\n';
            }
            cout << '\n';
        }
     
    }

 

D. Twist the Permutation

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

Problem - D - Codeforces

 

문제

 

a[i] = i 인 a 배열이 주어진다. i = 1부터 n까지 순서대로 각 i번째 prefix위치까지 오른쪽으로 cyclic shift 를 원하는 만큼 할 수 있을때 주어진 배열을 만들수있으면 i번째 cyclic shift를 한 횟수를 출력하고 아니라면 -1을 출력하는 문제

 

풀이

 

거꾸로 순서를 바꾸어 역추적하면서 하면 된다. 이후 최종적으로 만들어진 배열이 a배열이라면 답을 출력하고 아니라면 -1을 출력하면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    int a[2001];
    int b[2001];
    int ans[2001];
    void lshift(int idx, int num) {
        for (int i = 1; i <= idx; i++) {
            int tidx = i - num;
            while (tidx < 1) {
                tidx += idx;
            }
            b[tidx] = a[i];
        }
        for (int i = 1; i <= idx; i++)a[i] = b[i];
    }
    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];
            for (int i = n; i > 0; i--) {
                int num;
                for (int j = 1; j <= i; j++) {
                    if (i == a[j]) {
                        num = j;
                        break;
                    }
                }
                if (num == i)num = 0;
                ans[i] = num;
                if (num == 0)continue;
                lshift(i, num);
            }
     
            bool flag = true;
            for (int i = 1; i <= n; i++) {
                if (a[i] != i) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                for (int i = 1; i <= n; i++)cout << ans[i] << ' ';
                cout << '\n';
            }
            else cout << -1 << '\n';
        }
     
    }

 

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

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