일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
- vue3
- 레지스터
- E - Hanging Hearts
- 리버싱
- 2022
- django
- Round 866
- 밑바닥부터 시작하는 딥러닝 1
- dart
- 인하대 프로그래밍 경진대회
- Graph Cost
- vue-google-login
- 카카오 API
- idpiframe_initialization_failed
- Good Bye 2022: 2023 is NEAR
- list_display
- Flutter
- 1557
- Codeforces Round 831 (Div. 1 + Div. 2)
- Hello 2023
- Div. 2
- 코드포스
- 넥토리얼
- iupc
- 앳코더
- expand item
- 기본키 변경
- shake!
- 카카오 로그인
- 알고리즘 대회
- Today
- Total
pseong
코드포스 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';
}
}
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
AtCoder Beginner Contest 250 F - One Fourth (0) | 2022.05.10 |
---|---|
코드포스 Codeforces Round #751 (Div. 2) 풀이 (0) | 2021.10.30 |
코드포스 Codeforces Round #750 (Div. 2) 풀이 (0) | 2021.10.25 |
코드포스 Codeforces Round #741 (Div. 2) 풀이 (0) | 2021.10.20 |
코드포스 Codeforces Round #742 (Div. 2) 풀이 (0) | 2021.10.18 |