Codeforces Round #715 (Div.1, Div. 2)

A - Average Height

Problem - A - 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 main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        vector <int> a[2];
        for (int i = 0; i < n; i++)
        {
            int x; cin >> x;
            a[x % 2].push_back(x);
        }
 
        for (int k = 0; k < 2; k++)
            for (int x : a[k]) cout << x << ' ';
        cout << '\n';
    }
}

---

B - TMT Document

Problem - B - Codeforces

\(n\)길이의 문자열 \(s\)가 주어진다. 이 문자열은 'T', 'M'으로만 이루어져 있다.

\(s\)를 \(\frac n3\)개의 "TMT"로 나눌 수 있는지 알아내야 한다.

 

먼저 'T'가 'M'의 두배여야 한다.

각 'M'에 대하여, 왼쪽에서 \(x\)번째 'M'의 왼쪽에 \(x\)개 이상의 'T'가 존재하는지,

오른쪽에서 \(x\)번째 'M'의 오른쪽에 \(x\)개 이상의 '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; }
 
int n;
string s;
int Tsum[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> s;
 
        for (int i = 1; i <= n; i++)
        {
            if (s[i - 1] == 'T') Tsum[i] = 1;
            else Tsum[i] = 0;
 
            Tsum[i] += Tsum[i - 1];
        }
 
        if (Tsum[n] * 3 != n * 2)
        {
            cout << "NO\n";
            continue;
        }
 
        bool ans = true;
 
        int Mcnt = 0;
        for (int i = 1; i <= n; i++)
        {
            if (s[i - 1] == 'M')
            {
                ++Mcnt;
                if (Tsum[i - 1] < Mcnt) ans = false;
            }
        }
 
        Mcnt = 0;
        for (int i = n; i >= 1; i--)
        {
            if (s[i - 1] == 'M')
            {
                ++Mcnt;
                if (Tsum[n] - Tsum[i] < Mcnt) ans = false;
            }
        }
 
        cout << (ans ? "YES" : "NO") << '\n';
    }
}

---

C - The Sports Festival

Problem - C - Codeforces

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

이 수열의 원소들을 새로운 수열 \(b\)에 추가하려고 한다.

추가할 때마다, \(b\)에서 가장 큰 값 - \(b\)에서 가장 작은 값 만큼의 비용이 든다.

\(a\)의 모든 원소를 \(b\)에 추가하려고 할 때, 필요한 최소 비용을 구해야 한다.

 

 

\(a\)를 정렬하자.

관찰을 통해, 현재 구간 \(a[l..r]\)의 원소들을 모두 \(b\)에 추가했다면,

다음으로는 \(a_{l-1}\)또는 \(a_{r+1}\)을 \(b\)에 추가하는 것이 이득임을 알 수 있다.

 

\(DP_{l,r} : \) \(a[l..r]\)의 원소를 \(b\)에 추가한 상태에서 최소 비용

으로 DP식을 세우면 \(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;
ll s[2001];
ll psum[2001];
ll dp[2001][2001];
 
ll solve(int l, int r)
{
    if (l >= r) return 0;
 
    ll& ret = dp[l][r];
    if (ret != -1) return ret;
 
    ret = psum[r] - psum[l];
    ret += min(solve(l + 1, r), solve(l, r - 1));
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    memset(dp, -1, sizeof dp);
 
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> s[i];
 
    sort(s, s + n);
    for (int i = 1; i < n; i++)
        psum[i] = psum[i - 1] + (s[i] - s[i - 1]);
 
    ll ans = solve(0, n - 1);
    cout << ans << '\n';
}

---

A - Binary Literature

Problem - A - Codeforces

\(2n\)길이의 이진 문자열 3개가 주어진다.

이 중 적어도 2개의 문자열을 부분 수열로 가지면서, 길이가 \(3n\)이하인 문자열을 출력해야 한다.

 

0의 개수가 둘 다 \(n\)개 이상이거나, 1의 개수가 둘 다 \(n\)개 이상인 2개의 문자열이 무조건 존재한다.

0의 개수가 둘 다 \(n\)개인 문자열 \(s1, s2\)가 존재한다고 하면,

0의 개수를 \(n\)개로 고정시키고, 사이사이에 1을 최대 \(n\)개 추가로 적절히 집어넣어서 두 문자열이 모두 부분 수열이 되도록 만들 수 있다.

 

#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;
string s[3];
int cnt[3];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        cin >> s[0] >> s[1] >> s[2];
 
        cnt[0] = cnt[1] = cnt[2] = 0;
 
        for (int i = 0; i < n * 2; i++)
        {
            for (int k = 0; k < 3; k++)
                if (s[k][i] == '0') cnt[k]++;
        }
 
        string s1, s2;
        char x = 0;
 
        if ((cnt[0] >= n) == (cnt[1] >= n))
        {
            s1 = s[0];
            s2 = s[1];
            if (cnt[0] >= n) x = '0';
            else x = '1';
        }
        else if ((cnt[1] >= n) == (cnt[2] >= n))
        {
            s1 = s[1];
            s2 = s[2];
            if (cnt[1] >= n) x = '0';
            else x = '1';
        }
        else
        {
            s1 = s[0];
            s2 = s[2];
            if (cnt[0] >= n) x = '0';
            else x = '1';
        }
 
        string ans;
 
        int p1 = 0, p2 = 0;
        while (p1 < n * 2 && p2 < n * 2)
        {
            if (s1[p1] == s2[p2])
            {
                ans += s1[p1];
                p1++; p2++;
            }
            else if (s1[p1] == x)
            {
                ans += s2[p2++];
            }
            else
            {
                ans += s1[p1++];
            }
        }
 
        for (int i = p1; i < n * 2; i++) ans += s1[i];
        for (int i = p2; i < n * 2; i++) ans += s2[i];
 
        cout << ans << '\n';
    }
}

---

B - Almost Sorted

Problem - B - Codeforces

어떤 수열 \(a\)가 모든 인덱스 \(i\)에 대해 \(a_{i+1} \ge a_i-1\)을 만족한다면, 이 수열을 almost sorted하다고 한다.

\(n\)길이의 almost sorted한 모든 순열에 대해, 사전 순으로 \(k\)번째 순열을 출력해야 한다.

 

먼저 almost sorted한 순열은, 정렬된 순열에서 겹치지 않는 구간들을 적절히 골라 뒤집어주는 식으로 만들 수 있음을 알 수 있다.

사전순으로 빠른 순열을 만들려면,

1. 처음으로 수열을 뒤집기 시작하는 구간의 시작 인덱스가 뒤일수록 빠르다.

2. 그런 인덱스가 같다면, 처음으로 수열을 뒤집기 시작하는 구간의 끝 인덱스가 앞일수록 빠르다.

3. 그런 인덱스도 같다면, 2번째로 수열을 뒤집는 구간에서 1번부터 반복한다.

 

이 사실을 이용하면, 많아도 맨 뒤 60개 원소만이 뒤집어진다는 사실을 알 수 있다.

\(k\)값에 따라 뒤집어야 하는 구간을 찾은다음, 나이브하게 뒤집어 주면 된다.

 

#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; }
 
ll n, k;
ll ans[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> k;
        k--;
 
        if (n <= 61 && ((1ll << n - 1) <= k))
        {
            cout << "-1\n";
            continue;
        }
 
        for (int i = 0; i < n; i++) ans[i] = i + 1;
        int last = n;
        int ptr = n;
 
        for (int i = 0; i <= 60; i++)
        {
            ptr--;
            if (!(k & (1ll << i)))
            {
                reverse(ans + ptr, ans + last);
                last = ptr;
            }
        }
 
        for (int i = 0; i < n; i++) cout << ans[i] << ' ';
        cout << '\n';
    }
}

---

C - Complete the MST

Problem - C - Codeforces

\(n\)개의 정점과 \(m\)개의 간선으로 이루어진 가중치 그래프가 주어진다.

이 그래프는 완전 그래프인데, \(m\)개 이외의 간선은 아직 가중치가 설정되지 않았다.

 

남은 간선들의 가중치를 적당히 설정해 모든 가중치들을 xor한 값이 0이 되도록 하면서,

이 그래프의 MST의 가중치의 합이 최소값이 되도록 했을 때, 그 값을 구해야 한다.

 

 

우선, 추가로 할당되어야 하는 가중치를 \(w\)이라고 하자.

남은 간선 중 단 하나만 \(w\)의 가중치를 가지고, 나머지는 전부 0이 되도록 하면 무조건 이득임을 알 수 있다.

 

이제 2가지 경우로 나눠 생각하자.

 

1. 가중치가 설정되지 않은 간선에 사이클이 존재한다.

사이클은 \(n\)이 634보다 크다면 무조건 존재하며, 그렇지 않다면 \(n^3\)에 계산하면 된다.

 

그 사이클에 해당하는 간선 중 하나를 \(w\)로 설정하면, 이를 무시할 수 있음을 알 수 있다.

그러면 나머지 간선을 전부 0으로 설정하고, MST를 구하면 답이 된다.

 

 

2. 가중치가 설정되지 않은 간선에 사이클이 존재하지 않는다.

현재 가중치가 설정되지 않은 간선 중 하나가 \(w\)이고, 이 값을 최대한 줄여보자.

 

가중치가 이미 설정된 간선은 다음과 같이 3가지로 나눌 수 있다.

a. MST를 만들 때 필수적인 간선

b. MST를 만들 때 넣으면 안되는 간선

c. 둘 다 아닌 간선

 

c에 해당하는 간선은, 어떤 것을 선택하더라도 가중치가 설정되지 않은 간선 중 하나를 대체하여 MST를 만들 수 있음을 알 수 있다.

따라서 1번 경우와 같이 MST을 일단 만든 다음, c에 해당하는 간선 중 최소 가중치와 \(w\)중 작은 값을 추가하면 답이 된다.

 

#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; }
 
ll n, m;
 
set <pair<ll, pii> > mst;
set <pii> edges;
set <pii> pre_mst;
set <int> rm;
 
int par[200001];
 
void init()
{
    for (int i = 1; i <= n; i++) par[i] = i;
}
 
int getPar(int x)
{
    if (par[x] == x) return x;
    return par[x] = getPar(par[x]);
}
 
bool merge(int a, int b)
{
    a = getPar(a);
    b = getPar(b);
 
    if (a == b) return false;
 
    par[a] = b;
    return true;
}
 
ll graph[650][650];
int cache[200001];
void DFS(int v, int c)
{
    cache[v] = c;
    rm.erase(v);
 
    auto it = rm.begin();
    while (it != rm.end())
    {
        int nv = *it;
        if (edges.find({ min(v, nv), max(v, nv) }) == edges.end())
            DFS(nv, c);
 
        it = rm.upper_bound(nv);
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
 
    ll cxor = 0;
 
    for (int i = 0; i < m; i++)
    {
        ll u, v, w; cin >> u >> v >> w;
        if (u > v) swap(u, v);
        if (n < 634)
        {
            graph[u][v] = graph[v][u] = 1;
        }
        cxor ^= w;
 
        mst.insert({ w, {u, v} });
        edges.insert({ u,v });
    }
 
    init();
    for (auto it : mst)
    {
        ll w = it.first;
        int a = it.second.first;
        int b = it.second.second;
 
        if (merge(a, b))
            pre_mst.insert({ a,b });
    }
 
    for (int i = 1; i <= n; i++) rm.insert(i);
 
    int cur = 0;
    for (int i = 1; i <= n; i++)
    {
        if (cache[i]) continue;
        DFS(i, ++cur);
    }
 
    bool hasCycle = false;
    if (n >= 634) hasCycle = true;
    else
    {
        for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++)
        {
            if (graph[i][j]) continue;
            for (int k = j + 1; k <= n; k++)
            {
                if (!graph[i][k] && !graph[j][k]) hasCycle = true;
            }
        }
    }
 
    ll mn = 1e18;
    ll ans = 0;
 
    init();
    for (auto it : mst)
    {
        ll w = it.first;
        int a = it.second.first;
        int b = it.second.second;
 
        if (pre_mst.find({ a,b }) == pre_mst.end()) continue;
        a = cache[a], b = cache[b];
 
        if (merge(a, b)) ans += w;
        else mn = min(mn, w);
    }
 
    if (!hasCycle) ans += min(mn, cxor);
 
    cout << ans;
}

---

D - Swap Pass

Problem - D - Codeforces

추가 예정

---

E - Tree Calendar

Problem - E - Codeforces

추가 예정

---

F - Optimal Encoding

Problem - F - Codeforces

추가 예정