Codeforces Round #738 (Div. 2)

https://codeforces.com/contest/1559

Dashboard - Codeforces Round #738 (Div. 2) - Codeforces

 

 

 

오랜만에 스피드포스 라운드!

최근에 똥을 싸면서 1474 -> 1409 ->1284 로 떨어지는 수직낙하(?!)를 겪고 난 후라 조금 긴장한 상태로 시작했다.

하지만 생각보다 C번과 D1번이 쉬워서 빠르게 풀어 좋은 점수를 받을 수 있었다.

많은 사람들이 D1번까지는 풀어서 최근에 친 코포중 가장 스피드포스가 아니었나 싶다.

118점이 올라 다시 민트로 복귀할 수 있었던 라운드...

 

 

 

A. Mocha and Math

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

Problem - A - Codeforces

 

n개의 수를 가지는 수열이 주어지는데 서로 몇번이고 bitwise AND 연산을 했을 때, 수열의 최댓값이 최소가 되는 수열에서 최댓값을 구하는 문제.

 

모든 수끼리 bitwise AND 연산을 하면 최솟값만으로 된 수열이 탄생하므로 모든 수끼리 bitwise AND 연산을 하면 되는 문제이다.

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
void solve()
{
    int n;
    cin >> n;
    vector<int> v(n, 0);
    for(int i=0;i<n;i++)
        cin >> v[i];
    sort(v.begin(), v.end());
    int ans = v[0];
    for(int i=1;i<n;i++)
        ans &= v[i];
    cout << ans << endl;
}
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int tc;
    cin >> tc;
    while(tc--)
    {
        solve();
    }
 
    return 0;
}

 

 

B. Mocha and Red and Blue

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

Problem - B - Codeforces

빨간색또는 파란색로 칠해저있는 퍼즐과 아무색도 칠해지지않은 퍼즐이 있다.

빨간색은 'R', 파란색은 'B'. 칠해지지않은 퍼즐은 '?'이다.

이때 인접한 퍼즐이 같은 색이라면 불완전하다고 하고 이를 수치(불완전성이라고 하겠음.)로 나타낼 수 있다.

칠해지지않은 퍼즐을 모두 칠했을 때, 불완전성이 가장 낮은 퍼즐을 찾는 문제이다.

 

이 문제는 그리디하게 BFS로(?) 해결했다.

칠해지지 않은 퍼즐이 아니면 모두 queue에 넣은 뒤, queue에 들어있는 퍼즐들을 시작으로 양쪽으로 칠해지지않은 퍼즐이라면 해당 퍼즐과 다른색을 칠하였다.

 

개인적으로 상당히 비효율적으로 풀었다고 생각한다.

그리고 모두 칠해지지않을 때를 처리하지 않아서 1번 틀리고 로직에 문제가 있는 줄 알고 헤매었다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
 
    if(n == 1)
    {
        if(s[0] == '?') cout << "B" << endl;
        else cout << s << endl;
        return;
    }
 
    queue<pair<char, int>> q;
    int w = 0;
    for(int i=0;i<n;i++)
    {
        if(s[i] == 'B' || s[i] == 'R') q.push({s[i], i});
        else w++;
    }
    if(w == n)
    {
        for(int i=0;i<n;i++)
        {
            if(i%2) s[i] = 'B';
            else s[i] = 'R';
        }
        cout << s << endl;
        return;
    }
    while(!q.empty())
    {
        char curr = q.front().first;
        int index = q.front().second;
        q.pop();
        if(index > 0 && s[index-1] == '?')
        {
            if(curr == 'B')
            {
                s[index-1] = 'R';
                q.push({'R', index-1});
            }
            else
            {
                s[index-1] = 'B';
                q.push({'B', index-1});
            }
        }
        if(index < n-1 && s[index+1] == '?')
        {
            if(curr == 'B')
            {
                s[index+1] = 'R';
                q.push({'R', index+1});
            }
            else
            {
                s[index+1] = 'B';
                q.push({'B', index+1});
            }
        }
    }
    int imf = 0;
    for(int i=1;i<n;i++)
    {
        if(s[i] == s[i-1]) imf++;
    }
    cout << s << endl;
    //cout << imf << endl;
}
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int tc;
    cin >> tc;
    while(tc--)
    {
        solve();
    }
 
    return 0;
}

 

C. Mocha and Hiking

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

Problem - C - Codeforces

n+1 개의 도시가 있고 2n-1개 단방향 도로가 있다.

n-1개의 도로들은 i번째 도시로부터 i+1번째 도시로 연결되어있다. (1 <= i <= n-1)

n = 5일때 다음과 같이 연결되어있는 것이다. ( 1 -> 2 -> 3 -> 4 -> 5 6)

 

나머지 n개의 도로들은 다음과 같은 규칙을 가지고 있다.

n개의 수를 가지고 있는 수열이 있을 때, i번째 수가 0이면 i번째 도시에서부터 n+1번째 도시로 연결된 도로가 존재하고, i번째 수가 0이 아니면 n+1번째 도시에서부터 i번째 도시로 연결된 도로가 존재한다.

 

이 때, 모든 도시를 순회할 수 있는 순서로 도시 번호를 출력하면 된다.

 

불가능하면 -1을 출력하라지만 불가능한 경우가 없는 문제이다.

n = 5일때를 예시로 들어보자.

 

첫번째 수가 0이 아니면 6 -> 1 -> 2 -> 3 -> 4 -> 5 가 성립한다.

마지막 수가 0이면 1 -> 2 -> 3 -> 4 -> 5 -> 6 이 성립한다.

그리고 i번째 수가 0, i+1번째 수가 0이 아니면 i번째 도시와 i+1번째 도시 사이에 n+1번째 도시를 끼워넣으면 된다.

i = 3이라면 1 -> 2 -> 3 -> 6 -> 4 -> 5 가 성립한다.

 

정리를 하자면,

1. 첫번째 수가 0이 아닐때

2. 마지막 수가 0일때

3. 0 다음 수가 0이 아닐 때

 

모든 경우에 성립한다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
void solve()
{
    int n;
    cin >> n;
    vector<int> v(n, 0);
    for(int i=0;i<n;i++)
        cin >> v[i];
 
    if(v[n-1] == 0)
    {
        for(int i=1;i<=n+1;i++)
            cout << i << ' ';
        cout << endl;
        return;
    }
    else if(v[0] != 0)
    {
        cout << n+1 << ' ';
        for(int i=1;i<=n;i++)
            cout << i << ' ';
        cout << endl;
        return;
    }
 
    int index = -1;
    for(int i=0;i<n-1;i++)
    {
        if(v[i] == 0 && v[i+1] != 0)
        {
            index = i+1;
            break;
        }
    }
    if(index == -1)
    {
        cout << -1 << endl;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        cout << i << ' ';
        if(i == index) cout << n+1 << ' ';
    }
    cout << endl;
}
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int32_t tc;
    cin >> tc;
    while(tc--)
    {
        solve();
    }
 
    return 0;
}

D1. Mocha and Diana (Easy Version)

https://codeforces.com/contest/1559/problem/D1

Problem - D1 - Codeforces

 

Mocha와 Diana는 같은 수의 노드를 가지고 있고, 각각의 forest를 가지고 있다.

이 때, Mocha와 Diana가 u, v 노드를 연결했을 때도 cycle을 형성하지 않고 트리 또는 forest를 유지하면 된다.

연결될 수와 u, v 노드들을 출력하면 된다.

 

Union-find 자료구조를 사용해서 사이클 여부를 확인하면서 서로 다른 모든 노드들을 확인한다.

N^2번만에 모든 노드들을 확인해보면 된다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
class DISJOINT_SET
{
public:
    vector<int> parent;
    
    DISJOINT_SET(int size)
    {
        parent.assign(size+1, 0);
        for(int i=1;i<=size;i++)
            parent[i] = i;
    }
    int find(int v)
    {
        if(parent[v] == v) return v;
        return parent[v] = find(parent[v]);
    }
    void merge(int u, int v)
    {
        u = find(u);
        v = find(v);
        if(u == v) return ;
        parent[v] = u;
    }
};
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    DISJOINT_SET Mocha(n+1), Diana(n+1);
    int u, v;
    for(int i=0;i<m1;i++)
    {
        cin >> u >> v;
        Mocha.merge(u, v);
    }
 
    for(int i=0;i<m2;i++)
    {
        cin >> u >> v;
        Diana.merge(u, v);
    }
 
    vector<pair<int, int>> ans;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if((Mocha.find(i) != Mocha.find(j)) && (Diana.find(i) != Diana.find(j)))
            {
                Mocha.merge(i, j);
                Diana.merge(i, j);
                ans.push_back({i, j});
            }
        }
    }
    cout << ans.size() << endl;
    for(size_t i=0;i<ans.size();i++)
        cout << ans[i].first << ' ' << ans[i].second << endl;
    return 0;
}

 

총 노드의 수인 n의 최대가 1000이었기에 가능했던 방법이다.

D2문제는 n의 최대가 10만이다;;