Educational Codeforces Round 127 (Rated for Div. 2) 1463 → 1577

https://codeforces.com/contest/1671

Dashboard - Educational Codeforces Round 127 (Rated for Div. 2) - Codeforces

 

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

 

A. String Building

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

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

문제

 

a와b로 이루어진 string s가 주어진다. aa와 aaa, bb와 bbb들의 조합을 가지고 주어진 스트링을 만들 수 있으면 YES 아니라면 NO를 출력하는 문제

 

풀이

 

2와 3의 더하기 조합으로는 50이하의 어떤 숫자든 만들 수 있으므로 , 길이가 1인 a나 b만 없으면 YES 아니라면 NO를 출력하면 된다.

 

코드

 

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

 

B. Social Distance

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

Problem - B - Codeforces

 

문제

 

x축 위에 n개의 서로다른 양수 정수 좌표를 가진 point가 오름차순으로 주어진다. 각 point당 a[x]= a[x]+r or a[x] or a[x]-1을 만드는 opreation을 최대 1번 할 수 있는데 모든 포인트를 consecutive segment로 만들 수 있으면 YES 아니라면 NO를 출력하는 문제 

 

풀이

 

시작점에서 -1, 0 , +1 의 케이스를 총 3번 돌면서 가능한 경우가 한개라도 있는지 체크하고 없으면 NO를 출력한다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    int a[200001];
    int n;
    bool solve(int start) {
        bool ret = true;
        for (int i = 1; i < n; i++) {
            int start2 = start + 1;
            if ((start2 >= (a[i] - 1)) && (start2 <= (a[i] + 1))) {
                start = start2;
            }
            else {
                ret = false;
                break;
            }
        }
        return ret;
    }
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            cin >> n;
            for (int i = 0; i < n; i++)cin >> a[i];
            bool flag = false;
            for (int i = -1; i <= 1; i++) {
                if (solve(a[0] + i) == true) {
                    flag = true;
                    break;
                }
            }
            if (flag)cout << "YES\n";
            else cout << "NO\n";
        }
    }

C. Dolce Vita

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

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

문제

 

n개의 가게가 있다. 각 가게마다 a[i]원의 설탕을 하루에 1개씩 판다. 하루의 수입은 x원이고 이를 하루에 다 쓰지 않는다면 나머지 금액은 초기화된다. n과 x , a[i]가 주어질 때 최대로 살 수 있는 설탕의 개수를 출력하는 문제

 

풀이

 

a[i]를 최대한 많이 살 수 있게 정렬하여 각 인덱스 i마다 최대로 살 수 있는 날들을 이분탐색으로 찾고 i= n ~ 1까지 역순으로 최대 날들을 계산해주어 더해주면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;
long long a[200001];
long long sum[200001];
long long d[200001];
const long long INF = 1000100001;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        long long n, x;
        cin >> n >> x;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        sort(a + 1, a + 1 + n);
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + a[i];
        }
        long long l = 0, r = INF;
        long long ans = 0;
        long long MAX = 0;
        for (long long i = n; i > 0; i--) {
            l = 0;
            r = INF;
            while (l <= r) {
                long long mid = (l + r) / 2LL;
                long long tsum = mid * i + sum[i];
                if (tsum <= x)l = mid + 1;
                else r = mid - 1;
            }
            d[i] = r + 1;
            long long dif = d[i] - MAX;
            ans += (dif * i);
            MAX = max(MAX, d[i]);
        }
        cout << ans << '\n';
        //for (int i = 1; i <= n; i++)cout << a[i] << ' ';
        //cout << '\n';
        //for (int i = 1; i <= n; i++)cout << d[i] << ' ';
        //cout << '\n';
    }
}

 

D. Insert a Progression

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

Problem - D - Codeforces

문제

 

n길이의 양의 정수 배열 a와 x가 주어진다. x는 1,2,...,x 까지 있고 이들을 a배열 안에 원하는 위치에 삽입할 수 있다. 모든 수를 삽입한 뒤 각 i= 1 ~ (n+x-1)까지 abs(a[i]-a[i+1])의 총합의 최소 값을 출력하는 문제

 

풀이

 

우선 a배열의 최소값을 l, 최대값을 r 이라고 한다면 l~r사이의 값들은 추가 비용 없이 추가할 수 있다. 나머지 수들은

각 위치에 넣었을때 최소 값을 구해서 더해주면 된다.

 

코드

    #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--) {
            long long n,x;
            cin >> n>>x;
            long long ans = 0;
            long long MIN = 300000, MAX = 0;
            for (int i = 1; i <= n; i++) {
                cin >> a[i];
                MIN = min(MIN, a[i]);
                MAX = max(MAX, a[i]);
            }
            for (int i = 2; i <= n; i++) {
                ans += abs(a[i] - a[i - 1]);
            }
            //cout << ans << '\n';
            if (MIN > x) {
                long long tmin = min(a[1] - 1, a[n] - 1);
                for (int i = 2; i < n; i++) {
                    tmin = min(tmin, (a[i] - 1) + (a[i + 1] - 1) - abs(a[i]-a[i+1]));
                }
                cout << ans + tmin << '\n';
                continue;
            }
            if (MIN > 1) {
                long long l = 1, r = MIN - 1;
                long long tmin = min(a[1] - l, a[n] - l);
                for (int i = 2; i < n; i++) {
                    tmin = min(tmin, (a[i] - l) + (a[i + 1] - l) - abs(a[i] - a[i + 1]));
                }
                ans += tmin;
            }
            if (MAX < x) {
                long long l = MAX + 1, r = x;
                long long tmin = min(r - a[1], r - a[n]);
                for (int i = 2; i < n; i++) {
                    tmin = min(tmin, (r - a[i]) + (r - a[i + 1]) - abs(a[i] - a[i + 1]));
                }
                ans += tmin;
            }
            cout << ans << '\n';
        }
    }

 

 

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

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