코드포스 Codeforces Round #738 (Div. 2) 풀이

1559A - Mocha and Math

어떤 두 수 A, B를 AND 연산을 한다면 항상 그 결괏값은 MIN(A, B) 보다 같거나 작다.

 

왜냐하면 AND연산은 0은 무조건 0이 되는 마스크 역할을 하고 1은 0 또는 1이 될 수 있기 때문이다.

 

따라서 다른 숫자와 ADN 연산을 많이 하면 할수록 수는 적거나 같아질 수밖에 없다.

 

주어진 조건에서 모든 원소를 모든 원소와 AND연산을 할 수 있다.

 

따라서 정답은 모든 원소를 AND 연산한 값이 된다.

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define F first
#define S second
int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
 
    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        int ans=-1;
        for(int i=0; i<n; i++) {
            int a;
            cin >> a;
            if(ans==-1) ans = a;
            else ans &= a;
        }
        cout << ans << '\n';
    }
}

---

1559B - Mocha and Red and Blue

전부? 인 경우는 RBRBRB... 를 출력해주면 된다.

 

아닌 경우에는 순서대로 먼저 채워진 문자를 확인 후 양옆에 붙어있는?를 번갈아 가면서 채우면 된다.

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define F first
#define S second
 
int n;
string s;
int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
 
    int T;
    cin >> T;
    while(T--) {
        cin >> n >> s;
        bool fin=false;
        for(int i=0; i<n; i++) {
            if(s[i]!='?') {
                int go=i;
                fin = true;
                while(go-1>=0 && s[go-1]=='?') {
                    s[go-1] = s[go]^('B'^'R');
                    go--;
                }
                go = i;
                while(go+1<n && s[go+1]=='?') {
                    s[go+1] = s[go]^('B'^'R');
                    go++;
                }
            }
        }
        if(!fin) {
            s[0] = 'B';
            cout << 'B';
            for(int i=1; i<n; i++) {
                s[i] = s[i-1]^('B'^'R');
                cout << s[i];
            }
        }
        else cout << s;
        cout << '\n';
    }
}

---

1559C - Mocha and Hiking

1번 노드가 1인 경우(n+1번 노드에서 1번 노드로 갈 수 있는 경우)

 

n+1부터 방문하면 된다. 따라서 순서는 (n+1)→1→2→⋯→n

 

n번 노드가 0인 경우(n번 노드에서 n+1번 노드로 갈 수 있는 경우)

 

1번부터 방문하면 된다. 따라서 순서는 1→2→⋯→n→(n+1)

 

둘 다 아닌 경우

 

처음으로 1이 등장하는 노드를 i번 노드라고 하자(n+1번 노드에서 갈 수 있는 가장 작은 노드가 i번 노드라고 하자.)

 

1번 노드부터 i-1번까지 방문한 후 n+1번 노드를 갔다가 다시 i번부터 n번 노드까지 방문하면 된다.

 

1→2→⋯→i→(n+1)→(i+1)→(i+2)→⋯n

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define F first
#define S second
 
const int N=10000;
int n, an[N+10];
vector<int> v;
int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
 
    int T;
    cin >> T;
    while(T--) {
        cin >> n;
        v.clear();
        for(int i=1; i<=n; i++) {
            cin >> an[i];
            if(an[i]==1) v.push_back(i);
        }
        if(v.size()==0) {
            for(int i=1; i<=n+1; i++) {
                cout << i << ' ';
            }
            cout << '\n';
            continue;
        }
        if(v[0]!=1) {
            for(int i=1; i<v[0]; i++) {
                cout << i << ' ';
            }
            cout << n+1 << ' ';
            for(int i=v[0]; i<=n; i++) {
                cout << i << ' ';
            }
            cout << '\n';
            continue;
        }
        cout << n+1 << ' ';
        for(int i=1; i<=n; i++) {
            cout << i << ' ';
        }
        cout << '\n';
    }
}

---

1559D1 - Mocha and Diana (Easy Version)

두 개의 그래프에 사이클이 없도록 간선을 추가해야 하므로 분리 집합을 사용하면 된다. (union find)

 

주어진 각각의 그래프의 간선들을 unionParent를 수행한다.

 

여기서 주의할 점은 union find 집합을 한 개로 뭉치면 안되고 각 각 만들어야 한다.

 

그리고 1부터 n까지 노드에 만들수 있는 모든 간선을 조하면서 다음의 조건을 확인한다.

 

조건 1 : 연결하려는 두 노드가 첫 번째 그래프의 같은 집합이 아닌지

 

조건 2 : 연결하려는 두 노드가 두 번째 그래프의 같은 집합이 아닌지

 

두 조건을 만족하면 unionParent를 수행해 준 다음 간선 정보를 저장해주고 출력해주면 답이다.

 

시간 복잡도 : O(n^2)

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define F first
#define S second
 
const int N=1000;
int parent[N+10];
int parent2[N+10];
 
int getParent(int i) {
    if(i==parent[i]) return i;
    return parent[i] = getParent(parent[i]);
}
 
int getParent2(int i) {
    if(i==parent2[i]) return i;
    return parent2[i] = getParent2(parent2[i]);
}
 
void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if(a>b) swap(a, b);
    parent[b] = a;
}
 
void unionParent2(int a, int b) {
    a = getParent2(a);
    b = getParent2(b);
    if(a>b) swap(a, b);
    parent2[b] = a;
}
 
bool findParent(int a, int b) {
    return getParent(a)==getParent(b);
}
 
bool findParent2(int a, int b) {
    return getParent2(a)==getParent2(b);
}
 
int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
 
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    for(int i=1; i<=n; i++) {
        parent[i] = i;
    }
    for(int i=1; i<=n; i++) {
        parent2[i] = i;
    }
 
    for(int i=0; i<m1; i++) {
        int u, v;
        cin >> u >> v;
        unionParent(u, v);
    }
    for(int i=0; i<m2; i++) {
        int u, v;
        cin >> u >> v;
        unionParent2(u, v);
    }
 
    vector<pii> ans;
    for(int i=1; i<=n; i++) {
        for(int j=i+1; j<=n; j++) {
            if((!findParent(i, j)) && (!findParent2(i, j))) {
                unionParent(i, j);
                unionParent2(i, j);
                ans.push_back({i, j});
            }
        }
    }
    cout << ans.size() << '\n';
    for(int i=0; i<ans.size(); i++) {
        cout << ans[i].F << ' ' << ans[i].S << '\n';
    }
}

---

1559D2 - Mocha and Diana (Hard Version)

D1과 문제가 같지만 시간 복잡도 n^2에 풀면 시간 초과가 난다.

 

따라서 선택하려는 두 노드를 선택할 때 이중 반복문으로 하면 안 된다.

 

아이디어는 한 노드를 기준으로 일단 그래프를 묶는 것이다.

 

D1에서 봤듯이 사이클이 있으면 안 되므로 분리 집합을 이용한다.

 

일반적으로 분리 집합을 이용해서 노드를 합치면 더 작은 노드가 부모가 된다.

 

따라서 제일 작은 1번 노드를 기준으로 생각해보자.

 

먼저 1번 노드를 2~n번 노드까지 연결할 수 있으면 연결해 준다.

 

이러한 작업을 (a) 작업이라고 하자.

 

이렇게 연결을 완료하면 모든 노드의 상태는 다음과 같다.

 

2~n번 노드는 무조건 왼쪽 그래프 또는 오른쪽 그래프 중 한 곳 이상에서 1번 노드와 연결이 되어 있다.

 

왜냐하면 x번 노드와 1번 노드를 연결시키지 못하는 경우는 이미 어느 한쪽에서 1번 노드와 연결이 되어있기 때문이다.

 

따라서 연결시킬 수 있어서 연결시키면 두 그래프 모드 1번 노드와 연결이 되고,

 

연결시킬 수 없으면 두 그래프 중 한 그래프가 1번 노드와 연결이 되어 있다는 것이다.

 

이렇게 모든 노드를 최소한 한쪽에서 1번 노드와 연결을 시킨 다음,

 

왼쪽 그래프에서 1번 노드와 연결이 안 되어있는 노드들을 전부 vector나 stack안에 넣어준다.

 

여기서는 one에 넣어준다고 하자.

 

오른쪽 그래프에서 1번 노드와 연결이 안 되어있는 노드들을 전부 two에 넣어준다고 하자.

 

이제 one에 있는 노드들과 two에 있는 노드들을 연결시켜 주어야 한다.

 

여기서 one에 있는 노드와 two에 있는 노드끼리만 연결시켜줘도 문제의 조건을 만족하는가?라는 의문이 들 수 있다.

 

가장 중요하게 봐야 할 포인트는 다음과 같다.

 

2~n번 노드 중 아무 노드나 하나 선택했을 때 그 노드는 무조건 왼쪽 또는 오른쪽 그래프에서 1번 노드와 연결이 되어 있다. (이유는 이전에 설명했다)

 

(a) 작업을 끝낸 후 한쪽 그래프가 다음과 같이 존재한다고 하자.

이 그래프를 보면 연결될 가능성이 존재하는 노드(1번 노드와 연결이 안 되어있는 노드)는 3번 노드 하나다.

 

※ 1번 노드와 이미 연결이 되어있는 노드들은 연결할 수 있는 노드가 1번 노드와 연결이 안 되어있는 노드들이고, 1번 노드와 연결이 안 되어있는 노드들은 사이클만 생기지 않으면 모든 노드와 연결할 수 있기 때문에 1번 노드와 연결이 안 되어있는 노드들이 나중에 간선으로 연결될 수 있는 두 개 노드 중 한 개 노드를 무조건 포함한다.

 

3번 노드는 이 그래프에서 1번 노드와 연결이 안돼있으므로, 반대편 그래프에서는 1번 노드와 연결이 돼있다.

 

그렇다면 반대편 그래프의 3번노드는 1번 노드와 연결이 돼있으므로 생길 수 있는 간선은 반대편 그래프에서 1번 노드와 연결이 안 되어있는 노드들이다.

 

결국 종합해 보면 왼쪽 그래프에서 1번 노드와 연결이 안 되어있는 노드에서 오른쪽 그래프에서 1번 노드와 연결이 안 되어있는 노드 사이의 간선이 추가될 수 있는 간선들이다.

 

이제 one과 two 중에서 둘 중 하나가 전부 빌 때까지 반복문을 수행해 준다.

 

순서는 편하게 one의 back노드 와 two의 back노드를 연결해 주면 된다. (순서는 상관없다. 하지만 제거하기 편한 노드가 가장 마지막에 추가한 노드이기 때문이다.)

 

one의 back 노드와 two의 back 노드를 연결시켜주면 두 개의 노드 모두 반대편 그래프에서 1번 노드와 연결이 되어있기 때문에 두개의 노드는 무조건 1번 노드와 연결이 된다. 따라서 두개의 노드를 제거시켜 주어야 한다.

 

여기서는 pop을 이용해 쉽게 제거할 수 있다.

 

여기서 주의해야 할 점이 하나 존재하는데 두 개의 노드를 잇는 순간 분리 집합 원리에 의해 원래는 1번 노드에 포함이 안 되어있었지만 한쪽 노드가 1번 노드와 연결이 되어버리면서 연결이 될 수도 있다.

 

예를 들자면 다음 그림과 같다.

여기에서 2번 노드가 1번 노드와 연결이 되면 기존의 1번 노드와 연결이 안 되어있는 3번 노드도 1번 노드와 연결이 된다.

 

따라서 반복문을 돌 때에 분리 집합 부모 찾는 함수를 이용해서 자기 자신의 부모가 1인 경우 노드를 계속 제거해 주면서 1과 연결이 안 된 노드가 나올 때까지 제거해 주어야 한다.

 

이런 원리로 노드들을 전부 제거해 주다가 한쪽 vector가 비면 반복문을 멈춘다.

 

여기서 항상 vector가 비워질까?라는 의문이 들 수 있다.

 

두 개의 vector에서 1번과 연결이 안 되어있으면 연결시켜주고 노드를 제거해 주므로 한개의 vector라도 비어있지 않다면 연결해 줄 수 있는 간선이 존재한다는 뜻이고 계속 간선들을 연결시켜 주다보면 결국 한쪽 vector 또는 두개 vector가 비게 될 것이다.

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define F first
#define S second

const int N=100000;
int parent[N+10];
int parent2[N+10];

int getParent(int i) {
    if(i==parent[i]) return i;
    return parent[i] = getParent(parent[i]);
}

int getParent2(int i) {
    if(i==parent2[i]) return i;
    return parent2[i] = getParent2(parent2[i]);
}

void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if(a>b) swap(a, b);
    parent[b] = a;
}

void unionParent2(int a, int b) {
    a = getParent2(a);
    b = getParent2(b);
    if(a>b) swap(a, b);
    parent2[b] = a;
}

bool findParent(int a, int b) {
    return getParent(a)==getParent(b);
}

bool findParent2(int a, int b) {
    return getParent2(a)==getParent2(b);
}

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);

    int n, m1, m2;
    cin >> n >> m1 >> m2;
    for(int i=1; i<=n; i++) {
        parent[i] = i;
    }
    for(int i=1; i<=n; i++) {
        parent2[i] = i;
    }

    for(int i=0; i<m1; i++) {
        int u, v;
        cin >> u >> v;
        unionParent(u, v);
    }
    for(int i=0; i<m2; i++) {
        int u, v;
        cin >> u >> v;
        unionParent2(u, v);
    }

    vector<pii> ans;
    vector<int> one;
    vector<int> two;
    for(int i=2; i<=n; i++) {
        if((!findParent(i, 1)) && (!findParent2(i, 1))) {
            unionParent(i, 1);
            unionParent2(i, 1);
            ans.push_back({i, 1});
        }
        if(getParent(i)!=1) {
            one.push_back(i);
        }
        if(getParent2(i)!=1) {
            two.push_back(i);
        }
    }
    
    while(!one.empty() && !two.empty()) {
        if(getParent(one.back())==1) {
            one.pop_back();
            continue;
        }
        if(getParent2(two.back())==1) {
            two.pop_back();
            continue;
        }
        ans.push_back({one.back(), two.back()});
        unionParent(one.back(), two.back());
        unionParent2(one.back(), two.back());
    }

    cout << ans.size() << '\n';
    for(int i=0; i<ans.size(); i++) {
        cout << ans[i].F << ' ' << ans[i].S << '\n';
    }
}