티스토리 뷰

공부

2019.09.13 problem solving

구사과 2019.09.12 20:48

추석에 BOJ에서 13문제 연습 셋을 만들고 풀기로 결심했다. 아직은 그렇다 ㅋㅋ!

문제

9월 9일

K. 빛의 왕과 거울의 미로 2

비트 DP와 비슷한 식으로 한 줄에 대한 상태를 저장하는데, 단순한 불리언 변수로는 부족하니까 연결 상태에 대한 union-find를 메모이제이션하는 느낌으로 해결할 수 있는 문제다. 최근에 jh05013님이 Connection Profile DP라는 이름으로 포스팅하였으니 이 글을 참고하면 좋을 것 같다.

시작점과 끝점이 아주 판타스틱하게 주어지기 때문에 고통스러울 것이라고 예상했으나, 짜 보니 그렇게 힘들지는 않은 문제였다. 그래도 다이아 1 정도는 되는 거 같다. 암튼 채널보단 확실히 쉽다.

9월 11일

A. Bridge Park

옛날에 풀이까지 알고 있던 문제였으나 다 까먹어서 다시 생각했다. 그래도 대충 키워드를 알아서 금방 생각한듯..

새로 잇는 간선이 $(i, (i+1) \mod n)$ 만을 잇는다고 생각해 줄 수 있다. 증명은 모르겠는데 그냥 대충 해 보면 다른 경우에서는 이상하다는 것을 알 수 있다. 자명히 그냥 다 이으면 낭비가 심하다. 근데 일단 이어지지 않은 걸 다 이어주고 생각해 보자. Outer face에 모든 정점이 다 닿으면 Dual은 트리이다. 간선을 지우면 특정한 face가 외면에 "노출"된다. 에지의 양 쪽 face가 외면에 "노출"된 것이 그 에지가 Bridge인 것과 필요충분이다. 고로 간선을 최소로 추가해서 = 어떠한 face를 외면으로부터 막아서, 모든 에지에 대해 양 쪽 face중 하나가 노출되지 않도록 해야 한다. Outer face에 관해서 몇 가지 처리해야 할 사항이 있으나 결론적으로 이는 Minimum Vertex Cover 문제여서 트리 DP로 해결된다.

참 좋은 문제다.

D. Justice for All

Constructive라 쫄았는데 생각보다 어렵지 않았다. Typical한, $n$ 짜리 그래프로 $2n, 2n+1$ 만들기가 된다. $2n$ 은 그냥 길이 4의 사이클을 만들어 주면 되니까 쉽다. $2n+1$ 을 하려면 $2n$ 을 하면서 추가적인 매칭을 하나 더 이어줘야 한다. 사이클을 만들 때 그냥 만들지 말고 기존 컴포넌트에 연결되게 붙여주자 ($(n - 1, n)$ 같은 절선 간선을 하나 넣어서) 이제 $(1, n)$ 사이에 에지를 이이어 주자. 절선 간선을 이쁘게 넣어주면, 이 $(1, n)$ 간선을 사용하는 유일한 완벽 매칭이 하나 추가된다.

E. Farm and Factory

잘 안돼서 풀이를 봤는데 뭔가 모델링 자체가 좀 이상했던 듯... 일단 Farm만 있다고 하자. Dijkstra를 돌려주면, $C_u + C_v + dist(1, v) \geq dist(1, u)$ 같은 식이 나온다. 이를 모든 $u, v$ 에 대해서 정리하면 대략 다음과 같은 문제가 된다.

일직선 상 $x = dist(1, i)$ 위치에 점이 $N$ 개 있다. 이들을 중심으로 하는 구간을 각각 만들어서, 구간 길이 합을 최소로 해 주면서 모든 구간이 겹치게 할 수 있을까?

겹치는 점을 $dist(1, i)$ 의 중간값으로 잡아주면 된다. Factory가 있을 때도 비슷한데, 이 때는 45도 축변환 아이디어가 필요하다.

9월 12일

문제를 풀려고 시도했으나 한 문제도 풀지 못했다.

9월 13일


바빠서 많이 풀지는 못했다.

M. Farm Village

전날에 고생했던 문제인데 오늘 보니까 그렇게 어렵지 않았다. 이러한 유형의 문제에서는 MCMF를 진짜 돌리는 그리디 풀이법도 있고, DP 함수의 볼록성을 사용한 slope trick 풀이도 있다. 이 문제에서는 slope trick을 사용하여 DP 배열의 변홧값 배열을 관리하면 Heap만 사용해서 관리가 되어서 그렇게 했다. 볼록함수에서 DP 돌리는 것에 뭔가 심오한 게 있는 것 같은데 최근 좀 알아봐야 겠다는 생각을 했다..

9월 14일

일과 시간엔 바빴고, 밤에는 코드포스만 참가하고 잤다.

9월 15일

GP of Warsaw를 참가할 계획이다.

댓글
댓글쓰기 폼
공지사항
Total
267,608
Today
310
Yesterday
629