Codeforces Round #656 (Div. 3)

A - Three Pairwise Maximums

Problem - A - Codeforces

세 정수 \(x,y,z\)가 주어진다.

 

이 때, 다음을 만족하는 세 정수가 존재하는지 여부를 알아내고, 존재한다면 출력해야 한다.

\(x = \max(a,b)\), \(y = \max(a,c)\), \(z = \max(b,c)\)

 

먼저, \(a,b,c\)중 가장 큰 수를 \(a\)라고 가정하자.

그러면 \(x,y,z\)중 두 수는 \(a\)여야 한다.

 

따라서 \(x,y,z\)중 두 수가 같고 (이를 \(x,y\)라고 가정하자), \(z\)가 \(x,y\)보다 크지 않다면 해가 존재하며,

해는 \(x, z, 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 main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        ll x, y, z; cin >> x >> y >> z;
 
        bool ans = true;
        ll a, b, c;
        if (x == y)
        {
            if (z > x) ans = false;
            else
            {
                a = x;
                b = z;
                c = 1;
            }
        }
        else if (y == z)
        {
            if (x > y) ans = false;
            else
            {
                c = y;
                a = x;
                b = 1;
            }
        }
        else if (z == x)
        {
            if (y > z) ans = false;
            else
            {
                b = z;
                c = y;
                a = 1;
            }
        }
        else ans = false;
 
        if (!ans) cout << "NO\n";
        else
        {
            cout << "YES\n";
            cout << a << ' ' << b << ' ' << c << '\n';
        }
    }
}

---

B - Restore the Permutation by Merger

Problem - B - Codeforces

\(n\) 길이의 순열이 있는데, 이 순열 두 개를 합병하여 얻은 \(2n\)길이의 배열이 주어진다.

이 배열을 이용해 원래 순열을 복원해야 한다.

 

앞에서부터 배열을 순회하면서, 처음 나오는 수들을 차례로 모으면 원래 순열이 된다.

 

#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--)
    {
        set <int> st;
        vector <int> ans;
 
        int n; cin >> n;
        for (int i = 0; i < 2 * n; i++)
        {
            int a; cin >> a;
            if (st.find(a) == st.end()) ans.push_back(a);
            st.insert(a);
        }
 
        for (int it : ans) cout << it << ' ';
        cout << '\n';
    }
}

---

C - Make It Good

Problem - C - Codeforces

\(n\)길이의 배열 \(a\)가 있다.

이 배열에서 최소크기의 prefix를 제거하여, 배열이 다음 조건을 만족하도록 해야 한다.

 

- 배열의 맨 앞 또는 맨 뒤 원소를 제거 한다음, 새로운 배열의 맨 뒤에 추가하는 연산을 계속 했을 때,

새로운 배열을 비내림차순으로 정렬할 수 있다.

 

 

위 조건을 만족하기 위해서는 남은 배열을 둘로 나눴을 때, 왼쪽은 비내림차순 정렬되어있고, 오른쪽은 비오름차순 정렬되어있는 경우가 존재해야 한다는 사실을 알 수 있다.

 

맨 뒤 원소부터 위의 조건을 어디까지 만족하는지 확인한다음, 조건을 만족하지 않는 원소부터 자르면 된다.

 

#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];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
 
        bool flag = false;
        int ans = 0;
 
        for (int i = n - 2; i >= 0; i--)
        {
            if (!flag)
            {
                if (a[i] < a[i + 1])
                {
                    flag = true;
                }
            }
            else
            {
                if (a[i] > a[i + 1])
                {
                    ans = i + 1;
                    break;
                }
            }
        }
 
        cout << ans << '\n';
    }
}

---

D - a-Good String

Problem - D - Codeforces

\(n\)길이의 문자열 \(s\)가 주어진다. \(n = 2^k\)꼴이다.

 

\(s\)는 다음 중 하나를 만족하면 \(c\)-good 한 문자열이라고 한다.

1. \(s\)의 길이가 1이고, 문자 \(c\)를 포함한다.

2. \(s\)의 길이가 1보다 크고, 왼쪽 절반은 전부 문자 \(c\)이고, 오른쪽 절반은 \(c+1\)-good 한 문자열이다.

3. \(s\)의 길이가 1보다 크고, 오른쪽 절반은 전부 문자 \(c\)이고, 왼쪽 절반은 \(c+1\)-good 한 문자열이다.

 

\(s\)를 'a'-good 문자열로 바꾸기 위해 바꿔야 하는 문자의 최소 개수를 알아내야 한다.

 

 

단순 구현 문제이다.

2번과 3번 각각에 경우에 대해 바꿔야 하는 문자열의 몇개인지 재귀 등으로 구현하면 된다.

한번의 재귀마다 확인해야 하는 길이가 절반으로 줄어드므로, 많아도 \(\log 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;
 
int solve(int l, int r, char c) // [l,r)
{
    if (c > 'z') return 987654321;
    if (l + 1 == r)
    {
        if (s[l] == c) return 0;
        else return 1;
    }
 
    int ans = 0;
    int lans = 0, rans = 0;
    for (int i = l; i < l + (r - l) / 2; i++)
    {
        if (s[i] != c) lans++;
    }
    for (int i = l + (r - l) / 2; i < r; i++)
    {
        if (s[i] != c) rans++;
    }
 
    ans = 987654321;
    ans = min(ans, lans + solve(l + (r - l) / 2, r, c + 1));
    ans = min(ans, solve(l, l + (r - l) / 2, c + 1) + rans);
 
    return ans;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> s;
        cout << solve(0, n, 'a') << '\n';
    }
}

---

E - Directing Edges

Problem - E - Codeforces

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

간선중 일부는 방향이 주어져있고, 나머지는 방향이 주어져있지 않다.

 

방향이 정해져 있지 않은 간선에 방향을 정해서, 그래프를 DAG로 만들 수 있는지 여부를 판별하고,

가능하다면 그 해를 출력해야 한다.

 

먼저 방향이 정해지지 않은 간선이 없다고 생각하고, 가능한 위상정렬을 한가지 만들자.

위상정렬이 존재하지 않는다면 이미 DAG가 아니므로 불가능하다.

 

그리고 방향이 정해지지 않은 모든 간선에 대해, 아까 정한 위상정렬의 순서대로 간선의 방향을 정해주면 된다.

 

#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, m;
vector <pii> ndir;
 
vector <pii> graph[200001];
int cache[200001];
 
vector <int> stk;
bool DFS(int v)
{
    cache[v] = 1;
    for (auto it : graph[v])
    {
        int nv = it.first;
        if (cache[nv] == 0)
        {
            if(DFS(nv)) return true;
        }
        else if (cache[nv] == 1) return true;
    }
 
    cache[v] = 2;
    stk.push_back(v);
 
    return false;
}
 
int dist[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> m;
 
        ndir.clear();
        stk.clear();
 
        for (int i = 1; i <= n; i++) graph[i].clear(), dist[i] = -1;
 
        for (int i = 0; i < m; i++)
        {
            int d, u, v; cin >> d >> u >> v;
            if (d == 0) ndir.push_back({ u,v });
            else graph[u].push_back({ v,1 });
        }
 
        for (int i = 1; i <= n; i++) cache[i] = 0;
 
        bool ans = true;
        for (int i = 1; i <= n; i++)
        {
            if (!cache[i])
            {
                if (DFS(i)) ans = false;
            }
        }
 
        if (!ans)
        {
            cout << "NO\n";
            continue;
        }
 
        for (pii e : ndir)
        {
            int u = e.first, v = e.second;
            graph[u].push_back({ v, 0 });
            graph[v].push_back({ u, 0 });
        }
 
        reverse(stk.begin(), stk.end());
 
        for (int i = 0; i < stk.size(); i++)
        {
            int v = stk[i];
            dist[v] = i;
        }
 
        int cnt = stk.size();
 
        cout << "YES\n";
        for (int v = 1; v <= n; v++)
        {
            for (auto it : graph[v])
            {
                int nv = it.first;
                int d = it.second;
 
                if (dist[v] < dist[nv]) cout << v << ' ' << nv << '\n';
            }
        }
    }
}

---

F - Removing Leaves

Problem - F - Codeforces

\(n\)개의 정점으로 이루어진 트리가 주어진다.

 

트리에 다음과 같은 연산을 할 수 있다.

- \(k\)개의 리프가 같은 정점에 연결되어 있다면, 이 리프와 연결된 간선을 모두 삭제한다.

 

이 연산을 최대 몇 번 할 수 있는지 알아내야 한다.

 

 

관찰을 통해, 연산을 하는 순서와는 상관없이 답이 일정하게 나옴을 알 수 있다.

그 다음은 단순 구현이다. \(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; }
 
int n, k;
set <int> graph[200001];
set <int> cleaf[200001];
 
bool cache[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
        {
            graph[i].clear();
            cleaf[i].clear();
        }
 
        for (int i = 0; i < n - 1; i++)
        {
            int u, v; cin >> u >> v;
            graph[u].insert(v);
            graph[v].insert(u);
        }
 
        for (int i = 1; i <= n; i++)
        {
            if (graph[i].size() == 1)
            {
                for (int nv : graph[i]) cleaf[nv].insert(i);
            }
        }
 
        queue <int> q;
        for (int i = 1; i <= n; i++)
        {
            if (cleaf[i].size() >= k)
            {
                q.push(i);
                cache[i] = 1;
            }
        }
 
        int ans = 0;
        while (!q.empty())
        {
            int v = q.front(); q.pop();
            cache[v] = 0;
 
            while (cleaf[v].size() >= k)
            {
                ans++;
                for (int i = 0; i < k; i++)
                {
                    int nv = *cleaf[v].begin();
                    cleaf[v].erase(nv);
                    cleaf[nv].erase(v);
 
                    graph[v].erase(nv);
                    graph[nv].erase(v);
                }
            }
 
            if (graph[v].size() == 1)
            {
                for (int nv : graph[v])
                {
                    cleaf[nv].insert(v);
                    if (cleaf[nv].size() >= k && !cache[v])
                    {
                        q.push(nv);
                        cache[v] = 1;
                    }
                }
            }
        }
 
        cout << ans << '\n';
    }
}

---

G - Columns Swaps

Problem - G - Codeforces

\(2 \times n\)크기의 표가 있다. 표에는 \(1\)이상 \(n\)이하의 정수가 쓰여 있다.

한 열에 있는 두 수의 위치를 바꾸는 연산을 할 수 있을 때,

두 행이 모두 \(n\)길이의 순열을 이루도록 하기 위한 연산 횟수의 최소값을 구해야 한다.

 

먼저 \(1\)부터 \(n\)까지의 정수가 모두 정확히 2번 등장하지 않는다면, 불가능하다.

그렇지 않으면 무조건 가능하다는 것을 관찰로써 알 수 있다.

 

각 열을 여러개의 그룹으로 나누자.

각 그룹은 각 행에 쓰인 수들이 정확히 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;
int a[200001], b[200001];
vector <pii> idx[200001];
 
int cache[200001];
vector <int> stk;
int ans[200001];
void DFS(int v, int c)
{
    if (cache[v]) return;
 
    cache[v] = 1;
    stk.push_back(v);
 
    ans[v] = c;
 
    int ca = a[v], cb = b[v];
    for (int i = 0; i < 2; i++)
    {
        if (idx[ca][i].first != v)
        {
            if (idx[ca][i].second == 0) DFS(idx[ca][i].first, 1 - c);
            else DFS(idx[ca][i].first, c);
        }
 
        if (idx[cb][i].first != v)
        {
            if (idx[cb][i].second == 1) DFS(idx[cb][i].first, 1 - c);
            else DFS(idx[cb][i].first, c);
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            idx[i].clear();
            cache[i] = 0;
        }
 
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            idx[a[i]].push_back({ i,0 });
        }
 
        for (int i = 1; i <= n; i++)
        {
            cin >> b[i];
            idx[b[i]].push_back({ i,1 });
        }
 
        bool hasAns = true;
        for (int i = 1; i <= n; i++)
        {
            if (idx[i].size() != 2) hasAns = false;
        }
 
        if (!hasAns)
        {
            cout << "-1\n";
            continue;
        }
 
        vector <int> res;
        for (int i = 1; i <= n; i++)
        {
            if (cache[i]) continue;
 
            stk.clear();
            DFS(i, 0);
 
            int cnt = 0;
            for (int v : stk)
            {
                if (ans[v] == 0) cnt++;
            }
 
            if (cnt * 2 > stk.size())
            {
                for (int v : stk) if (ans[v] == 1) res.push_back(v);
            }
            else
            {
                for (int v : stk) if (ans[v] == 0) res.push_back(v);
            }
        }
 
        cout << res.size() << '\n';
        for (int v : res) cout << v << ' ';
        cout << '\n';
    }
}