Codeforces Round #669 (Div. 2)

A - Ahahahahahahahaha

Problem - A - Codeforces

0과 1로만 이루어진 길이 \(n\)인 배열 \(a\)가 주어진다. (n은 짝수)

이 배열에서 최대 \(\frac n2\)개의 원소를 제거해서, 홀수번째 인덱스의 수의 합과 짝수번째 인덱스의 수의 합이 같도록 해야 한다.

 

0과 1의 개수를 센다. 각각 \(cnt_0, cnt_1\)이라고 하자.

0이 \(\frac n2\)개 이상 있다면, 0을 \(cnt_0\)개 출력하면 된다.

그렇지 않다면, 1을 \(\lfloor \frac {cnt_1}2 \rfloor\ \times 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 main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        int cnt[2] = { 0,0 };
        for (int i = 0; i < n; i++)
        {
            int x; cin >> x;
            cnt[x]++;
        }
 
        if (cnt[0] >= n / 2)
        {
            cout << cnt[0] << '\n';
            for (int i = 0; i < cnt[0]; i++) cout << "0 ";
            cout << '\n';
        }
        else
        {
            cout << cnt[1] / 2 * 2 << '\n';
            for (int i = 0; i < cnt[1] / 2 * 2; i++) cout << "1 ";
            cout << '\n';
        }
    }
}

---

B - Big Vova

Problem - B - Codeforces

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

이 배열의 수들을 적절히 재배치하여 만든 배열을 \(b\)라고 하자.

배열 \(c\)를 다음과 같이 정의하자.

\(c_i = GCD(b_1,\cdots,b_i)\)

 

\(c\)가 사전순으로 가장 크게 되도록하는 \(b\)를 알아내야 한다.

 

그리디하게, 현재 만들 수 있는 가장 큰 수를 계속 해서 만들어내면 된다.

\(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;
int a[1001];
 
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];
 
        int g = 0;
        for (int i = 0; i < n; i++)
        {
            int res = 0;
            int idx = -1;
 
            for (int j = 0; j < n; j++)
            {
                if (a[j] == 0) continue;
                int tmp = gcd(g, a[j]);
                if (tmp > res)
                {
                    res = tmp;
                    idx = j;
                }
            }
 
            g = gcd(g, a[idx]);
            cout << a[idx] << ' ';
            a[idx] = 0;
        }
 
        cout << '\n';
    }
}

---

C - Chocolate Bunny

Problem - C - Codeforces

\(n\)길이의 순열 \(p\)가 있다.

최대 \(2n\)개의 쿼리를 사용하여, 원래 순열을 알아내야 한다.

 

각 쿼리마다 다음과 같은 정보를 알 수 있다.

두 인덱스 \(x, y\)에 대하여, \(p_x \bmod p_y\)

 

\(p_x < p_y\)라고 하면, 다음과 같은 사실을 알 수 있다.

\(p_x \bmod p_y = p_x\), \(p_y \bmod p_x < p_x\)

 

따라서 1번 인덱스부터 차례로, 현재 인덱스와 이전 인덱스 중 가장 큰 수가 있는 인덱스를 이용해 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 ans[10001];
int query(int x, int y)
{
    cout << "? " << x << ' ' << y << endl;
    int res; cin >> res;
    return res;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int n; cin >> n;
    int cmax = 1;
    for (int i = 2; i <= n; i++)
    {
        int r1 = query(cmax, i);
        int r2 = query(i, cmax);
 
        if (r1 > r2)
        {
            ans[cmax] = r1;
            cmax = i;
        }
        else
        {
            ans[i] = r2;
        }
    }
 
    ans[cmax] = n;
    cout << "!";
    for (int i = 1; i <= n; i++) cout << ' ' << ans[i];
    cout << endl;
}

---

D - Discrete Centrifugal Jumps

Problem - D - Codeforces

\(n\)개의 빌딩이 있다. 1번째 빌딩에서 시작해 \(n\)번째 빌딩으로 이동하려고 한다.

현재 빌딩에서 오른쪽에 있는 빌딩으로 이동하기 위해서는, 다음과 조건 중 하나를 만족해야 한다.

 

1. 두 빌딩 사이에 있는 빌딩들의 높이가 모두 두 빌딩보다 낮다.

2. 두 빌딩 사이에 있는 빌딩들의 높이가 모두 두 빌딩보다 높다.

 

\(n\)번째 빌딩으로 이동하기 위한 최소 이동 수를 알아내야 한다.

 

 

각 빌딩을 정점으로하고, 이동 가능한 빌딩 사이를 간선으로 잇는 그래프로 생각하자.

가능한 간선을 모두 추가한다음, BFS로 최단거리를 찾으면 된다.

 

가능한 간선을 찾는 방법에는 여러가지가 있다.

본인은 낮은(또는 높은) 빌딩부터 시작해 set에 차례로 추가한다음, set 내에서 좌우로 연결된 빌딩 끼리 간선을 이어주었다.

그러면 그래프의 간선이 많아도 \(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; }
 
const int N = 300001;
 
int n;
int h[N];
vector <pii> vec;
 
vector <int> graph[N];
int dist[N];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> h[i];
        vec.push_back({ h[i], i });
    }
 
    sort(vec.begin(), vec.end());
 
    set <int> st;
    for (int i = 0; i < vec.size();)
    {
        int val = vec[i].first;
        vector <int> tmp;
        while (i < vec.size() && vec[i].first == val)
        {
            tmp.push_back(vec[i].second);
            st.insert(vec[i].second);
            i++;
        }
 
        for (int idx : tmp)
        {
            auto it = st.find(idx);
            if (it != st.begin())
            {
                graph[*prev(it)].push_back(idx);
            }
            if (next(it) != st.end())
            {
                graph[idx].push_back(*next(it));
            }
        }
    }
 
    reverse(vec.begin(), vec.end());
    st.clear();
 
    for (int i = 0; i < vec.size();)
    {
        int val = vec[i].first;
        vector <int> tmp;
        while (i < vec.size() && vec[i].first == val)
        {
            tmp.push_back(vec[i].second);
            st.insert(vec[i].second);
            i++;
        }
 
        for (int idx : tmp)
        {
            auto it = st.find(idx);
            if (it != st.begin())
            {
                graph[*prev(it)].push_back(idx);
            }
            if (next(it) != st.end())
            {
                graph[idx].push_back(*next(it));
            }
        }
    }
 
    memset(dist, -1, sizeof dist);
    queue <int> q;
    q.push(0); dist[0] = 0;
    while (!q.empty())
    {
        int v = q.front(); q.pop();
        for (int nv : graph[v])
        {
            if (dist[nv] != -1) continue;
            dist[nv] = dist[v] + 1;
            q.push(nv);
        }
    }
 
    cout << dist[n - 1];
}

---

E - Egor in the Republic of Dagestan

Problem - E - Codeforces

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

간선은 흰색 또는 검은색으로 이루어져 있다.

 

각 정점의 색을 선택할 수 있다. (흰색 또는 검은색)

현재 정점에서 다른 정점으로 이동할 때, 현재 정점의 색과 간선의 색이 같은 경우에만 이동할 수 있다.

 

각 정점의 색을 적절히 선택해서, 1번 정점에서 \(n\)번 정점까지 이동할 수 없거나, 최단거리가 최대가 되도록 해야 한다.

 

\(n\)번 정점으로 들어오는 모든 간선에 대해 살펴보자.

어떤 \(x\)번 정점에서 \(n\)번 정점으로 가는 흰색 간선이 있다고 가정해보자.

그러면 \(x\)번 정점을 검은색으로 바꿔서 해당 간선을 사용하지 못하게 하는 것이 무조건 이득임을 관찰을 통해 알 수 있다.

 

도중에 이미 해당하는 정점의 색이 정해져서 어쩔 수 없이 간선이 생길 수도 있게 된다.

이런 경우에만 간선이 있다고 가정하면서 BFS를 해 나가면 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, m;
vector <pii> graph[500001];
int ans[500001];
int dist[500001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v, t; cin >> u >> v >> t;
        graph[v].push_back({ u,t });
    }
 
    memset(ans, -1, sizeof ans);
    memset(dist, -1, sizeof dist);
 
    queue <int> q; q.push(n);
    dist[n] = 0;
 
    while (!q.empty())
    {
        int v = q.front(); q.pop();
        for (auto it : graph[v])
        {
            int nv = it.first, t = it.second;
            if (dist[nv] != -1) continue;
 
            if (ans[nv] == -1) ans[nv] = 1 - t;
            if (ans[nv] == t)
            {
                dist[nv] = dist[v] + 1;
                q.push(nv);
            }
        }
    }
 
    cout << dist[1] << '\n';
    for (int i = 1; i <= n; i++)
    {
        if (ans[i] == -1) cout << 0;
        else cout << ans[i];
    }
}