Codeforces Round #650 (Div. 3)

A - Short Substrings

Problem - A - Codeforces

문자열 \(a\)가 있다.

\(b\)는 \(a\)의 연속된 길이 2의 부분문자열을 모두 이어 붙여서 만들어지는데,

주어지는 \(b\)를 이용해 \(a\)를 알아내야 한다.

 

\(b\)의 짝수번째 인덱스에 있는 문자들을 모두 출력한 다음, 맨 마지막 글자를 출력하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        string s; cin >> s;
        for (int i = 0; i < s.size(); i += 2) cout << s[i];
        cout << s.back() << '\n';
    }
}

---

B - Even Array

Problem - B - Codeforces

길이 \(n\)인 배열 \(a\)가 주어진다.

이 배열의 두 원소를 골라 위치를 바꾸는 연산을 할 수 있을 때,

그 원소의 홀짝성과 배열의 인덱스의 홀짝성이 모두 같도록 할 수 있는지 여부를 알아내고, 가능하다면 최소 연산횟수를 알아내야 한다.

 

홀수 인덱스에 있는 짝수의 개수와 짝수 인덱스에 있는 홀수의 개수를 각각 세자.

이 값이 다르다면 불가능하고, 같다면 이 개수가 답이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
 
        int odd = 0, even = 0;
        for (int i = 0; i < n; i++)
        {
            int a; cin >> a;
            if (i % 2 != a % 2)
            {
                if (i % 2) odd++;
                else even++;
            }
        }
 
        if (odd == even) cout << odd << '\n';
        else cout << "-1\n";
    }
}

---

C - Social Distance

Problem - C - Codeforces

\(n\)개의 테이블에 사람들이 앉아있다.
테이블의 사람들 사이의 거리를 \(k\)이상을 유지하면서 추가할 수 있는 최대 사람 수를 구해야 한다.

연속된 빈자리의 개수를 각각 세자.
각 연속된 빈자리의 개수에 대해 여기에 더 앉을 수 있는 사람 수를 하나의 식으로 나타낼 수 있다.

예를 들어, 양 쪽에 사람이 앉아있는 상태에서 연속된 빈자리의 개수가 \(cnt\)개 일 때,
더 앉을 수 있는 사람의 수는 \(\lfloor \frac {\max(0, cnt-2k)-1}{k+1} \rfloor + 1\)이다.

한 쪽만 앉아있을 때, 양 쪽다 앉아있지 않을 때도 각각 계산해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, k;
string s;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> k;
        cin >> s;
 
        int ans = 0;
        int cnt = 0;
        bool hasOne = false;
 
        int i = 0;
        for (; i < n; i++)
        {
            if (s[i] == '1')
            {
                hasOne = true;
                break;
            }
            cnt++;
            continue;
        }
 
        if (!hasOne)
        {
            cout << (cnt - 1) / (k + 1) + 1 << '\n';
            continue;
        }
 
        int tmp = max(0, cnt - k);
        if (tmp) ans += (tmp - 1) / (k + 1) + 1;
        cnt = 0;
 
        for (i++; i < n; i++)
        {
            if (s[i] == '1')
            {
                int tmp = max(0, (cnt - k * 2));
                if(tmp) ans += (tmp - 1) / (k + 1) + 1;
                cnt = 0;
            }
            else cnt++;
        }
 
        tmp = max(0, cnt - k);
        if (tmp)ans += (tmp - 1) / (k + 1) + 1;
 
        cout << ans << '\n';
    }
}

---

D - Task On The Board

Problem - D - Codeforces

알파벳 소문자로 이루어져 있는 문자열 \(s\)가 있다.

여기에서 적당한 문자들을 지운 다음, 재배열해서 새로운 문자열 \(t\)를 만든다.

 

\(m\)길이의 \(t\)를 이용해 배열 \(b\)를 만드는데,

\(b\)의 각 원소 \(b_i\)는 \(t_j \gt t_i\)를 만족하는 모든 인덱스 \(j\)에 대해, \(|i-j|\)의 합이다.

 

\(s\)와 \(b\)가 주어졌을 때, \(t\)를 복원해야 한다.

 

먼저 \(b_i=0\)인 모든 인덱스 \(i\)에 대해, \(t_i\)는 고른 문자 중에 가장 큰 문자임을 알 수 있다.

따라서 \(s\)에 있는 문자 중 \(b_i=0\)인 인덱스의 개수보다 크거나 같은 개수가 존재하는 문자 중 가장 큰 것이 \(t_i\)가 될 것이다.

 

그렇게 \(t_i\)를 정했다면, 모든 \(b\)의 원소 \(b_j\)에 대해 \(|i-j|\)를 빼주자.

 

이것을 \(t\)가 복원 될 때까지 반복하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
string s;
int cnt[26];
int m;
int b[51];
bool cache[51];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        memset(cnt, 0, sizeof cnt);
        memset(cache, 0, sizeof cache);
 
        cin >> s;
        for (char c : s) cnt[c - 'a']++;
 
        cin >> m;
        for (int i = 0; i < m; i++) cin >> b[i];
 
        int ptr = 25;
        char ans[51] = { 0, };
        while (true)
        {
            vector <int> idx;
            for (int i = 0; i < m; i++)
            {
                if (cache[i]) continue;
                if (b[i] == 0) idx.push_back(i);
            }
 
            if (idx.empty()) break;
 
            while (!cnt[ptr] || cnt[ptr] < idx.size()) ptr--;
 
            for (int i : idx)
            {
                cache[i] = 1;
                ans[i] = ptr + 'a';
                for (int j = 1; i - j >= 0; j++)
                    b[i - j] -= j;
                for (int j = 1; i + j < m; j++)
                    b[i + j] -= j;
            }
 
            ptr--;
        }
 
        cout << ans << '\n';
    }
}

---

E - Necklace Assembly

Problem - E - Codeforces

목걸이를 만들기 위한 \(n\)개의 구슬이 있다.

어떤 목걸이가 \(k\)번 회전해도 똑같은 모양이라면, 이 목걸이가 \(k\)-beautiful 하다고 하자.

 

\(n\)개의 구슬과 \(k\)가 주어졌을 때, \(k\)-beautiful 하게 될 수 있는 목걸이의 최대 길이를 알아내야 한다.

 

먼저 각각의 알파벳이 몇개씩 있는지 세고, 각각을 \(cnt_i\)라고 하자.

 

목걸이의 패턴이 \(m\)번 반복되도록 만든다고 생각해 보자.

그러면 한 패턴에 각 알파벳을 최대 \(\lfloor \frac {cnt_i}{m} \rfloor\)개씩 사용할 수 있고,

이 값들의 합이 한 패턴의 최대 길이가 된다. 이를 \(d\)라고 하자.

 

그러면 \(1 \le j \le d\)에 대해, \(k\)가 \(j\)로 나누어 떨어진다면 \(j \times m\)길이를 목걸이를 만들 수 있다는 뜻이 된다.

 

따라서 \(O(n^2)\)의 시간복잡도로 모든 경우를 계산할 수 있고, 이 중 최대값을 찾으면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, k;
string s;
int cnt[26];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        memset(cnt, 0, sizeof cnt);
 
        cin >> n >> k;
        cin >> s;
 
        for (char c : s) cnt[c - 'a']++;
 
        int ans = 0;
 
        for (int i = 1; i <= n; i++)
        {
            int res = 0;
            for (int j = 0; j < 26; j++)
            {
                res += cnt[j] / i;
            }
 
            if (res >= k) ans = max(ans, k * i);
            else
            {
                for (; res; res--)
                {
                    if (k % res == 0) ans = max(ans, res * i);
                }
            }
        }
 
        cout << ans << '\n';
    }
}

---

F - Flying Sort (Hard Version)

Problem - F2 - Codeforces

\(n\)길이의 배열 \(a\)가 주어진다.

 

이 배열에서 두 가지의 연산을 할 수 있다.

1. 임의의 원소를 배열의 맨 앞으로 옮긴다.

2. 임의의 원소를 배열의 맨 뒤로 옮긴다.

 

이 배열을 비내림차순으로 정렬하고자 할 때, 필요한 최소 연산 횟수를 구해야 한다.

 

먼저 수들을 좌표압축한다.

 

어떤 구간 \([l,r]\)에 해당하는 수를 수열에서 모두 선택했을 때, 이 수들이 정렬되어 있다고 하자.

그러면 이 수들을 제외한 수들을 연산을 이용해 정렬하면 될 것이다.

이 수들은 선형 시간에 찾을 수 있다.

 

이 때 연산을 사용하지 않아도 되는 수들이 있다.

위에서 선택한 수들의 인덱스가 최소 \(s\), 최대 \(e\)에 존재한다고 할 때,

\(s\)보다 작은 인덱스에 있는 \(l-1\)와, \(e\)보다 큰 인덱스에 있는 \(r+1\)은 연산하지 않아도 된다.

이 수들은 각각 이분탐색으로 찾을 수 있다.

 

이렇게 모든 경우에 대해 정렬되어있는 수의 개수를 \(res\)라고 하면, \(n-res\)의 최소값이 답이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
int a[200001];
vector <int> x;
vector <int> idx[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        x.clear();
 
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            x.push_back(a[i]);
            idx[i].clear();
        }
        idx[n].clear();
 
        sort(x.begin(), x.end());
        x.erase(unique(x.begin(), x.end()), x.end());
 
        for (int i = 0; i < n; i++)
        {
            int res = lower_bound(x.begin(), x.end(), a[i]) - x.begin();
            a[i] = res;
            idx[res].push_back(i);
        }
 
        int ans = 987654321;
 
        int s = 0;
        int last = -1;
        int sum = 0;
 
        for (int i = 0; i < x.size(); i++)
        {
            if (idx[i].front() > last)
            {
                sum += idx[i].size();
                last = idx[i].back();
 
                continue;
            }
 
            int e = i - 1;
 
            if (s) sum += lower_bound(idx[s - 1].begin(), idx[s - 1].end(), idx[s].front())
                - idx[s - 1].begin();
 
            sum += idx[e + 1].size()
                - (lower_bound(idx[e + 1].begin(), idx[e + 1].end(), idx[e].back()) - idx[e + 1].begin());
 
            ans = min(ans, n - sum);
 
            s = i;
            sum = idx[i].size();
            last = idx[i].back();
        }
 
        int e = x.size() - 1;
        if (s) sum += lower_bound(idx[s - 1].begin(), idx[s - 1].end(), idx[s].front())
            - idx[s - 1].begin();
 
        sum += idx[e + 1].size()
            - (lower_bound(idx[e + 1].begin(), idx[e + 1].end(), idx[e].back()) - idx[e + 1].begin());
 
        ans = min(ans, n - sum);
 
        for (int i = 0; i < n; i++)
        {
            int res = lower_bound(idx[a[i]].begin(), idx[a[i]].end(), i) - idx[a[i]].begin() + 1;
            res += idx[a[i] + 1].size()
                - (lower_bound(idx[a[i] + 1].begin(), idx[a[i] + 1].end(), i) - idx[a[i] + 1].begin());
 
            ans = min(ans, n - res);
        }
 
        cout << ans << '\n';
    }
}