20200803 PS

정말 우연히 친구들이 진행하는 스터디를 도강하고, 같이 세상과 연애하기 카페에 가서 문제들을 좀 더 풀었다.

 

Royal Questions

 

https://codeforces.com/contest/875/problem/F

 

Matroid 이론의 연습문제이다. 문제에서 왕자들을 정점으로 두고, 어떤 공주가 왕자 $a$, $b$를 동시에 골랐다면 두 왕자 $a$와 $b$를 간선으로 잇는다면 그래프가 만들어진다. Graph matroid와 비슷하게, 어떤 그래프 $G = (V, E)$에 대해 Ground set을 $E$로, Independent set를 $\left{ E' \in E : 그래프 (V, E')의 각 컴포넌트의 간선의 개수가 정점의 개수 이하 \right}$ 로 정의하면, $(E, I)$는 매트로이드가 된다. 여기서 최대 무게 독립집합을 구하는 간단한 그리디 알고리즘을 적용하면 문제를 풀 수 있다.

 

Greedy Gift Takers

 

https://www.acmicpc.net/problem/15456

 

관찰을 몇 번 하면 풀 수 있는 문제이다. 결론 자체는 매우 간단하지만, 거기까지 도달하는 데에 우여곡절을 겪을 수 있다. 내가 결론까지 도달한 사고방식을 자세히 서술한다.

 

관찰 1. 선물이 막히는 것은 몇 명이 트롤을 해서이다. 그게 한 명일 수도 있고(입력에 $N-1$ 이 있는 경우를 생각해 보라!), 여러 명이 합심해서 트롤하는 경우도 있다. 아무튼 누군가 트롤을 해서 어느 시점 이후로 줄을 꽉 막아버리면 그 뒤의 모두가 선물을 받지 못하게 되겠지만, 그렇지 않은 이상 결국은 모두가 언젠간 선물을 받게 될 것이다.

 

관찰 2. 혼자서 줄을 막으려면, 자신이 $N-1$이면 된다. 여러 명이서 합심해서 줄을 막으려면 어떻게 해야 하지? 일반적으로는 잘 모르겠으니 '둘이서 줄을 막으려면' 어떻게 해야 할지부터 생각해 보자. 둘이서 줄을 막으려면, 예를 들어, 붙어있는 두 명이 모두 $N-2$ 이면 된다. 그러면 두 명이서 계속 자리를 바꾸면서 번갈아서 선물을 받아먹을 것이다. 그렇지 않으면 줄을 막을 수 없을까? 둘 중 한 명이 $N-3$이라면? 그러면 나머지 한명이 $N-1$이 아닌 이상 줄을 못 막는다. (그러면 사실상 $N-1$ 혼자서 막는 것이긴 하지만 말이다) 그러니, 둘이서 줄을 막으려면 $N-2$ 이상이 두 명 붙어있어야 한다. 그러니, 이제 $k$ 명이서 줄을 막으려면 $N-k$이상이 $k$명 붙어있어야 한다는 추측을 할 수 있다. 그런 조건들이 첫번째로 만족하는 시점 이후의 누구도 선물을 받을 수 없다.

 

관찰 3. 이 아이디어를 코딩하고 디버깅하면서, 아이디어의 틀린 점을 발견한다. $N-k$ 이상이 $k$명 "붙어"있어야 할 필요는 없다. 그런 "줄막힘 유발자"들은, 붙어있지 않아도 다른 친구들을 밀어가면서 쌓이게 되어 있다. 그냥 줄의 앞부터 돌면서, "$N-k$ 이상의 사람을 $k$번째로 발견하게 된 $k$가 존재하는 순간" 멈추면 된다.

 

미지의 다각형

 

https://www.acmicpc.net/problem/2351

 

입코딩 난이도와 실제 코딩 난이도가 크게 차이나는 문제이다. 정말이지 구현하기 싫게 생겼다.

 

일단 문제를 푸는데 필수적인 아이디어는, degree가 2인 정점이 존재하며, 이 정점 양옆에 붙어있는 간선은 무조건 다각형의 변이라는 것이다. 그 다음에 하게 되는 생각은, 이 점에서 왼쪽으로 쭉 뻗어서 degree가 3 이상인 첫 정점을 찾고, 오른쪽으로 쭉 뻗어서 degree가 3 이상인 첫 정점을 찾으면, 이 두 정점을 잇는 간선이 존재하리라는 것이다. 물론 그런 간선이 항상 존재하리라는 보장은 없지만 (있다고 착각하면 망한다!), degree가 2인 정점 각각에 대해 "양 옆" 정점 쌍들을 모두 조사해보면, 그들 중 한 쌍은 이어져 있다. 이 성질을 이용해 쉽게 $O(N^2)$ 풀이를 얻을 수 있다. 맞은 사람들 중에는 나밖에 없는 것 같지만, 아무튼 이 풀이로도 쉽게 풀 수 있다.

 

여기서, "대각선의 특징"을 생각하지 않고, "대각선이 아닌 변들의 특징"을 생각하면 더 쉽고 빠른 풀이를 얻을 수 있다. 유니온 파인드를 끌어서 생각하자. degree가 2인 정점들로부터 시작해서 천천히 정점들을 합쳐나간다. 이 때, 이미 연결되어 있는 두 정점을 잇고 있는 간선은 대각선이다. 대각선이 아닌 변들은 연결되어 있지 않은 두 점을 잇는다. 마지막 간선을 제외하면. 이 성질을 이용하면 $O(N \alpha (N))$의 풀이를 얻을 수 있다.