2021년 1월 21일 PS 일지

1. Persistence Segment Tree 연습문제 풀이

www.acmicpc.net/problem/11932

11932번: 트리와 K번째 수

트리와 K번째 수 문제는 푸는 중이다

 

풀이 보기 전에 어제 풀었던 Component Tree 내용을 이용해 

O(N log^3 N) 풀이를 짰으나 장렬히 시간초과가 난다.

덕분에 LCA 복습했다 ^^

HLD로 비슷하게 할 수 있을 것 같으나 역시 시간초과가 예상된다.

 

잠깐 다른 과목 밸런스 맞추러 갑니다.

한동안 PS에 시간을 쏟아 부었다. 즐겁지만, 더 오래 PS를 하기 위해 다른 과목 간 밸런스를 맞추기로 결심했다.

이제 시간 투자도 체계적으로 할 것이다.

2. 이분그래프에서의 최대 매칭 = 최소 버텍스 커버

www.acmicpc.net/problem/12843

12843번: 복수전공

요 문제가 이분매칭이라는 글을 봐서
열심히 풀어봤는데, 아무리 봐도 이분매칭이 될 수가 없는거다. 다른 블로그의 풀이를 봐도 다 납득할 수 없는 말만 적어놨다. 그러던 중. 그린님의 글을 봤고 최소 버텍스 커버라는 키워드를 얻었다.

그걸 타고 넘어가서 갓 kks님의 글을 보는 중 ㅎㅎ

Kőnig's theorem

한국에서는 쾨닉의 정리라 읽는다.

쾨닉의 정리는 이분그래프의 최대 매칭의 수와 최소 버텍스 커버의 크기가 항상 일치한다는 정리다.

이 사실은 다음으로부터 증명된다.

1. 이분그래프의 최대 매칭으로 버텍스 커버를 얻어낼 수 있다.

2. 얻어낸 버텍스의 커버의 크기는 최소다.

 

일단 최대매칭으로부터 버텍스 커버를 얻어내는 방법은 다음과 같다.

주어진 이분그래프 G = {L , R , E}라 하자.

최대 매칭을 M*이라 할 때

{L-M*}에 속한 모든 정점으로부터 "alternating path"를 통해 도달할 수 있는 모든 정점을 X라 하자.

이때 alternating path란 M*에 포함되지 않은 간선, 포함된 간선, 포함되지 않은 간선... 순으로 포함 여부가 alternate하는 경로를 의미한다.

 

이때 C* = (L-X) ∪ (R∩X)가 우리가 구한 버텍스 커버다.

 

1,2 증명 글을 읽어봤는데 정말 어렵다.

추후 때가 되면 다시 도전한다.

3. ACL Library

내 깃허브에 대표적인 자료구조 및 알고리즘 템플릿이 올라와 있다.

그런데! Atcoder에서 만든 ACL Library란게 있더라 ㄷㄷ
atcoder.jp/posts/518

AtCoder Library (ACL) - AtCoder

진짜 사기다...
수학, 세그, 네트워크 플로우까지 대표적인 알고리즘의 구현이 모두 있다.

구현은 이걸로 공부하자. 매일 하나씩 하자!!
지금은 floor_sum 공부하는 중 - Complete

-> 한 일본인의 블로그에서 증명을 공부했다. rsk0315

 

원조:github.com/yosupo06/library-checker-problems

yosupo06/library-checker-problems