Codeforces Round #765 (Div. 2) 1645 -> 1652

Codeforces Round #765 (Div. 2)

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

 

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

 

A. Ancient Civilization

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

Problem - A - Codeforces

문제

 

길이가 n인 배열이 주어진다. 여기서 두 수의 거리란 2진수로 나타냈을 때 서로 다른 비트 자리의 갯수이다. 각 n개의 수들에서 거리 총합이 최소가 되는 수를 출력하는 문제

 

풀이

 

각 비트마다 1이 많은지 0이 많은지 수를 세서 많은쪽으로 맞춰서 출력한다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    long long a[101];
    long long bi[31];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            int n, l;
            cin >> n >> l;
            for (int i = 0; i < l; i++)bi[i] = 0;
            for (int i = 0; i < n; i++) {
                long long t;
                cin >> t;
                int start = 0;
                while (t) {
                    if (t % 2)bi[start]++;
                    start++;
                    t /= 2;
                }
            }
            long long start = 1, ans = 0;
            for (int i = 0; i < l; i++) {
                int t1 = bi[i], t2 = n - bi[i];
                if (t1 > t2)ans += start;
                start *= 2LL;
            }
            cout << ans << '\n';
        }
    }

 

 

B. Elementary Particles

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

Problem - B - Codeforces

 

문제

 

길이가 n인 배열이 주어진다. 이때 서로 다른 subsegment를 2개 뽑는데, 이들 중에서 무조건 같은 인덱스에 같은 숫자가 최소 1개라도 있어야한다. 이때 조건에 맞는 최대 subsegment의 길이를 출력하는 문제

 

풀이

 

각 같은 숫자들끼리 서로 인접한것들만 검사해서 각 subsegment 왼쪽에 최대 몇개가 올 수 있는지, 오른쪽에 최대 몇개가 올 수 있는지 계산해준다. 각 숫자 인덱스 기준으로 왼쪽 갯수 오른쪽갯수 min값으로 계산해주면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    int a[150001];
    vector<int> idx[150001];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            int n;
            cin >> n;
            int ans = -1;
            for (int i = 1; i <= n; i++) {
                cin >> a[i];
                idx[a[i]].clear();
            }
            for (int i = 1; i <= n; i++) {
                if (!idx[a[i]].empty()) {
                    int num = idx[a[i]].back();
                    int l1 = num - 1, r1 = n - num;
                    int l2 = i - 1, r2 = n - i;
                    if (ans == -1)ans = min(l1, l2) + min(r1, r2) + 1;
                    else ans = max(ans, min(l1, l2) + min(r1, r2) + 1);
                }
                idx[a[i]].push_back(i);
            }
            
            cout << ans << '\n';
        }
    }

C. Road Optimization

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

Problem - C - Codeforces

 

문제

 

0~l 까지 좌표가 있고, 정부는 0 -> l 으로 가는 최대한 빠른 시간에 도달할 도로를 만드려고 한다. n개의 좌표에는 속도 제한이 있는데 속도제한을 만난 시점부터 다음 지점까지는 d[i]의 속도로 가야한다. 그리고 k개의 속도 제한 지점을 없앨 수 있는데 첫번째 속도제한은 제거할 수 없다. 최대 k개를 지웠을 때 걸리는 최소 시간을 출력하는 문제

 

풀이

 

d[i][j]= i 본인 위치를 제외하고 앞에서 부터 0~j개를 지웠을때 l까지가는 최소 시간 으로 정의하고 O(N^3) dp로 답을 구한다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    long long sign[510], limit[510];
    long long d[510][510];
    long long n, l, k;
    const long long MAX = 10000LL * 200000LL;
    long long solve(int i, int j) {
        if (i > n)return 0;
        if (i == n)return (l - sign[n]) * limit[n];
        if (d[i][j] != -1)return d[i][j];
        d[i][j] = MAX;
        for (int start = i + 1; start <= n+1; start++) {
            int dif = start - i - 1;
            if (dif > j)break;
            d[i][j] = min(d[i][j], solve(start, j - dif) + (sign[start] - sign[i]) * limit[i]);
        }
        return d[i][j];
    }
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        memset(d, -1, sizeof(d));
        cin >> n >> l >> k;
        for (int i = 1; i <= n; i++)cin >> sign[i];
        for (int i = 1; i <= n; i++)cin >> limit[i];
        sign[n + 1] = l;
        cout << solve(1, k) << '\n';
    }

 

 

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

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