티스토리 뷰

Div. 1의 문제 2개를 풀어보았습니다. 링크: http://codeforces.com/contest/1198

[Div 1C/Div 2E] Matching vs. Independent Set

정점이 $3n$개인 그래프가 주어질 때 크기 $n$ 이상인 매칭 또는 크기 $n$ 이상인 독립집합 중 하나를 찾는 문제입니다.

 

둘 중에 하나를 찾으라는 문제는 처음 봐서, 일단 어느 한 쪽을 먼저 찾아보기로 생각하고 접근했습니다. 대충 말해서 일반적으로 "큰" 매칭을 찾는 것은 "쉬운($\mathcal{P}$)" 문제이지만, "큰" 독립집합을 찾는 것은 "어려운($\mathcal{NP}$-hard)" 문제입니다. 그래서 큰 매칭을 찾아보기로 생각했습니다.

Maximum matching을 찾는 것은 어려우니, maximal matching에 대해 생각해봤고, 다음과 같은 방식으로 문제를 해결할 수 있었습니다.

 

  1. Maximal matching을 아무거나 하나 찾습니다.

  2. 1에서 찾은 matching의 크기가 $n$ 이상이면 성공.

  3. 2가 아니라면, 1에서 찾은 matching에 포함되지 않는 $n$개 이상의 정점이 있고, 이들은 독립집합을 이루므로 성공.

위 알고리즘의 정당성은 다음과 같이 증명할 수 있습니다.

 

Theorem. 어떤 그래프 $G$ 의 maximal matching이 있을 때, 여기에 포함되지 않는 정점들은 독립집합을 이룬다.

proof) 귀류법으로 그렇지 않다고 합시다. 그러면 maximal matching에 포함되지 않는 두 정점 $u, v \in V(G)$가 존재해 $u$와 $v$를 잇는 $G$의 간선이 존재합니다. 그러면 $u-v$ 간선을 추가해도 matching이 되므로 maximality에 모순.

 

아래는 제 C++ 구현입니다.

#include <bits/stdc++.h>
using namespace std;
 
int N, M, T, cnt;
bool used[300005];
bool edge[500005];
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> T;
	while (T--){
		cin >> N >> M;
		memset(used, 0, sizeof(used[0])*(3*N+1));
		memset(edge, 0, sizeof(edge[0])*(M+1));
		cnt = 0;
		for (int i=1; i<=M; i++){
			int u, v;
			cin >> u >> v;
			if (!used[u] && !used[v]){
				used[u] = 1, used[v] = 1;
				edge[i] = 1;
				cnt++;
			}
		}
		if (cnt >= N){
			cout << "Matching" << '\n';
			int numout = 0;
			for (int i=1; i<=M&&numout<N; i++){
				if (edge[i]){
					++numout;
					cout << i << ' ';
				}
			}
			cout << '\n';
		}
		else{
			cout << "IndSet" << '\n';
			int numout = 0;
			for (int i=1; i<=3*N&&numout<N; i++){
				if (!used[i]){
					++numout;
					cout << i << ' ';
				}
			}
			cout << '\n';
		}
	}
}

Div 1D/Div 2F. Rectangle Painting 1

$n \times n$ 격자가 하나 주어집니다. 각각의 칸은 검은색 또는 흰색으로 칠해져 있습니다. 크기가 $h \times w$인 직사각형에 포함되는 모든 칸을 흰색으로 칠하는데 드는 cost는 $\max(h, w)$ 입니다. 이 때, 모든 칸을 흰색으로 만드는데 드는 최소 비용을 찾는 문제입니다.

 

그냥 제한이 작으니 $D(i,j,x,y)$를 "$(i, j)$와 $(x, y)$를 왼쪽 위/오른쪽 아래 점으로 하는 직사각형을 흰색으로 칠하는데 필요한 최소 비용"으로 정의하고 DP를 해주면 됩니다.

 

아래는 제 C++ 구현입니다.

 

#include <bits/stdc++.h>
using namespace std;
 
char A[51][51];
int N, D[51][51][51][51];
 
int f(int l, int r, int x, int y){
    if (D[l][r][x][y] >= 0) return D[l][r][x][y];
    if (l == x && r == y) return D[l][r][x][y] = (A[l][r] == '#');
    D[l][r][x][y] = max(x-l+1, y-r+1);
    for (int i=l; i<x; i++)
        D[l][r][x][y] = min(D[l][r][x][y], f(l,r,i,y)+f(i+1,r,x,y));
    for (int i=r; i<y; i++)
        D[l][r][x][y] = min(D[l][r][x][y], f(l,r,x,i)+f(l,i+1,x,y));
    return D[l][r][x][y];
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(D, -1, sizeof(D));
    cin >> N;
    for (int i=0; i<N; i++) cin >> A[i];
    cout << f(0,0,N-1,N-1) << endl;
}

'정보과학 > Codeforces' 카테고리의 다른 글

Codeforces Round #580  (1) 2019.08.19
Codeforces Round #578  (0) 2019.08.12
Codeforces Round #492  (0) 2019.08.06
Codeforces Round #576  (0) 2019.08.04
Codeforces Round 526 (Div 2) 후기  (0) 2018.12.11
Educational Codeforces Round 55 후기  (0) 2018.12.01
댓글
댓글쓰기 폼
공지사항
Total
19,595
Today
1
Yesterday
100