연습 250626

1. https://www.acmicpc.net/problem/32512

구사과님의 잘 비벼진 문자열 비빔밥이다. failure function으로 만든 트리에 대한 고찰이 잘 녹아있다. 문제는 그냥 잘 풀어서 풀이 생략.

 

중간에 모든 i에 대해 B[i..m]과 C의 longest common prefix를 구할 일이 있었다.

나는 해싱이분탐색을 썼다. 해싱 소수에 const를 안 붙였더니 시간이 많이 걸렸다. 선형로그 시간복잡도이다.

 

C[i..len(C)]와 C의 longest common prefix를 Zc, B[i..m]과 C의 longest common prefix를 Zb라고 하자.

Zc는 Z 알고리즘으로 구할 수 있다.

i=1부터 m까지 스위핑을 해서 Zb를 구하자. i+Zb[i]가 최대인 경우의 i와 i+Zb[i]를 L, R이라고 하자.

L <= i <= R인 경우, B[i, R]가 C의 substring이 되어서 Zb[i]를 바로 구할 수 있거나 (Zb[i]<R) Zb[i]>=R이다.

Z와 비슷하게 해주면 된다. 이러면 선형에 Zb를 구할 수 있다.

 

2. The 3rd Universal Cup. Stage 14: Harbin

(송씨 세린 나) 팀으로 하는 3번째 팀연습이다.

 

B번은 convex하지 않은 다각형에 대해 묻는 문제였다. Concave hull을 생각하면 좋은 방법은, 다각형을 이루는 점들로 만든 convex hull에서 바깥 가장자리에서 다각형을 빼주는거다.

concave한 polygon

 

임의의 다각형은 triangulation할 수 있다. 그래서 고정된 convex hull의 경우 최대 넓이 concave polygon은 적당한 삼각형을 빼주는거다.

한 가지 더 생각할 것은, concave polygon의 convex hull의 바깥에 있는 점을 하나 추가해도 여전히 concave하다는 것이다. 따라서 최적해의 convex hull은 그냥 모든 점의 convex hull이다.

 

 

I번 문제는 기묘한 문제이다. pi(ai) = n을 만족하는 2 이상의 ai의 가짓수를 number of multiplicative partitions of n이라고 부른다. n이 10^10 이하일 때는 최댓값이 10125 정도로, 굉장히 작다. 이걸 빠르게 나열해주면 뚫리는건지 풀리는건지 아무튼 잘 된다.

그럼 multiplicative partition을 어떻게 빠르게 구하냐? multiplicative partition은 소인수 감성으로 생각하면 multiset partition 문제로 환원된다. 이건 stack overflow가 해줬다. 근데 아직 안 읽어봤다. 읽어봐야겠다.

 

 

D번은 문자열 문제다. 송씨가 풀이의 핵심을 만들고 내가 그것을 완성시켰는데, 완성시키는 과정에서 살짝 삑사리가 났고, 나는 구현을 130줄 했기 때문에 구현에 문제가 있을 것이라고 생각했다. 여기에 longest common prefix를 해싱 이분탐색으로 해서 tle가 났고, 총체적 난국이었다. 앞으로는 어려운 문제의 경우 팀원들이랑 상의해서 풀이 검토를 받아야겠다.

그리고 sa + lcp를 팀노트에 넣어야겠다. suffix tree가 모든 것을 다 씹어먹어주는 줄 알았는데, suffix tree + dfs ordering + O(1) lca 짜는거보다는 그냥 sa + lcp 짜는게 999배는 쉬워보인다.

넣는 김에 z도 넣고 manacher도 넣고 eertree도 넣고 그냥 마구마구 넣어야겠다.

 

3. https://www.acmicpc.net/problem/34041

최근 문제 창을 보다가 읽었다. 챗지피티를 갈구니까 파푸스-굴딘 정리가 튀어나왔다. 결론적으로 ij로 생기는 다각형의 면적과 무게중심을 알아야 된다. 모스 알고리즘을 쓰는 줄 알고 알고리즘 분류를 열었더니 생각보다 멀쩡해서 prefix sum을 사용하는 고능한 풀이를 떠올렸다.