2020.06.28 Problem Solving

4주간의 학교 감금에서 드디어 탈출! 기숙사에서 PS할 시간도 별로 없었고 중간고사 기간까지 끼여있었지만, 기어코 PS를 해내는 나... 코포는 못해서 아쉬웠다.

이번에는 내가 학교에 있는 동안 푼 문제들에 대해 정리해보려고 한다. 생각해보니 푼 문제가 많아서 적을 만한 거만 적으려고 한다.

 

Fortune Telling 2 , 카드 공장 (Large)

 

같은 문제다. 카드 하나에 대해서만 생각을 해보면 그 카드에 적힌 숫자 두 개 모두보다 크거나 같은 수가 불린다면 무조건 뒤집힐 것이고, 둘 중 작은 수보다 작은 수가 불린다면 뒤집히지 않을 것이다. 그거 두 개가 아닌 중간 수가 불렸을 때가 중요한데 앞면이 작은 수일 때만 뒤집히므로 앞면이 둘 중 큰 수로 고정되게 된다.  그럼 마지막에 불린 '중간 수'를 잘 찾은 다음 둘 중 큰 수 이상으로 불린 수가 몇 번 불렸는지 세주면 된다. 자료구조를 잘 활용하면 되고, '중간 수'가 불리지 않는 경우도 예외처리해주자.

여담으로 중간고사 전날 국어시간에 자습을 줬을 때 푼 문제다. 뭐하는 새끼지?

 

평면그래프와 삼각형

 

단순 평면그래프의 성질. E<=3V-6. 이걸 극한으로 활용해주자. 일단 인접리스트를 set 등의 연결여부를 빠른 시간에 판단할 수 있는 자료구조로 구현해주자. 그리고 매번 차수가 가장 낮은 정점을 고른다. 이 정점의 차수는 항상 5 이하이다. (차수<=(6V-12)/V) 그럼 5C2가지의 정점쌍에 대해 모두 연결검사를 해주면 된다. 그리고 그 정점을 제거.

 

오리날다

 

랜덤으로 문제 뽑아서 풀기 메타의 시작이다. 문제를 다르게 해석한다면 점프한 후에 떨어지는 높이들의 합을 최소화하는 것으로 받아들일 수 있다. (S+떨어진 높이*2=이동거리) dp를 하자. dp[i]=i번 트램펄린까지 이동할 때 떨어지는 높이의 최솟값이다. 높이가 작은 트램펄린 i부터 그 트램펄린에 도달가능한 트램펄린 x들에 대해서 dp[i]=min(dp[x]+y[x]+h[x]-h[i])=min(dp[x]+y[x]-h[x])-h[i]이다. 세그먼트트리를 이용하여 풀면 된다. 최솟값 세그먼트트리를 이용하며 y[x]+h[x] 순서대로 정렬하여 노드를 배치하자.

 

Voronoi Diagram

 

엄청난 이름에 비하여 어렵지 않다. 간선은 항상 한 색깔로 칠해지거나 두 색깔에 의해 양분된다. 일단 다익스트라로 모든 정점들에 대해 그 정점에서 가장 가까운 '집합에 속한 점'과 그 거리를 구한다. 간선의 양끝점의 가장 가까운 점이 같다면 그 간선은 한 색깔로 색칠될 거고 아니라면 적당히 내분될 텐데 그건 거리를 통해 알아서 잘 구하자. 

 

Automorphisms

 

적당한 트리동형. 일단 항상 위치가 고정되는 정점을 찾는다. 나는 그걸 리프노드와의 거리가 가장 먼 정점으로 잡았으며, 이것은 항상 한 개 또는 인접한 두 개이다. 인접한 두 개일 때는 적당한 루트 하나를 그 중간에 붙여주면 된다. 나는 그렇게 구현은 안 했지만 그런 느낌으로 풀었다. 그리고 트리동형을 갈기면서 각 노드마다 서브트리에서 트리의 형태가 같은 서브트리가 a개 존재한다면 a!을 답에 곱해준다. a개와 b개가 존재한다면 a!*b!을 곱해주고... 대충 느낌 오리라 믿는다. 그럼 끝!

 

레드 블루 스패닝 트리 2

 

파란색이 최대일 때 : 파란색 간선들만으로 최대한 트리를 만들려 하고 파란색 컴포넌트들을 빨간색으로 연결할 때.

파란색이 최소일 때 : 반대

파랑 간선 개수가 그 사이에 있는지 먼저 확인한 다음 일단 파란색이 최소가 되게 트리를 형성한다. 그리고 이제 빨간색 간선들을 무시하고 파란색 간선들만 유파에서 정점을 뭉쳐준다. 유파에서 같은 집합에 속하지 않는 정점 두 쌍은 빨간색 간선이 하나 이상 존재하는 경로로 연결되어있을 것인데, 항상 그 빨간색 간선을 제거하고 파란색 간선을 그 사이에 연결해 스패닝 트리를 유지할 수 있다. 그러므로 k개가 될 때까지 계속해서 다른 집합에 속한 정점 두 쌍을 연결하는 간선을 추가하고 두 개를 합쳐주면 된다.

 

Saint John Festival

 

5만개의 점들에 대해 포인트 인 컨벡스 헐을 해야 된다. naive로 하면 5억이라 약간 애매한데, 확실하게 풀 수 있는 방법이 있다. 일단 컨벡스 헐을 구해두자. 그리고 여기서 분할 정복을 한다. 컨벡스 헐을 양분한 다음 양분하는 선을 기준으로 점들을 분류하여 재귀적으로 시행한다. 기저사례는 컨벡스 헐에 속한 정점이 세 개가 될 때로, 이때 naive하게 포인트 인 폴리곤을 해주면 된다. 시간복잡도는 O(LlogL+SlogL) 정도.

 

변호사들

 

간선이 양방향으로 모두 존재하지 않는다면 그냥 무조건 쓸 수 있다. 그것들을 치워주자. 그리고 그렇게 해서 변호받을 수 있게 된 변호사들에 대해서는 더이상 변호받을 필요가 없으므로 다 그 정점을 나가는 방향으로 방향을 바꿔주고, 반복...하여 이제 그래프에는 변호받지 못한 변호사들과 양방향 간선들밖에 없다. 이때 컴포넌트들 중 하나라도 트리라면 NO이고 아니면 YES이다. 대충 그림을 그려보면 느낌이 올 거다.

 

타워 디펜스

 

투샛. 구현은 복잡하다. 나는 16가지 케이스분류를 하여 8천 바이트를 짰다...

 

업적의 노예 2

 

조금만 생각해봐도 단순 키타마사로 풀린다.

 

안 적은 문제들까지 포함하면 학교에서 총 17문제를 풀었다. PS량과 반비례하는 내신 성적...