PS 이야기

길이가 $n$인 문자열 $s$가 있다. $1 \leq i \lt n$인 $i$에 대해 $z[i]$를 $i$에서 시작하는 suffix와 $s$의 가장 긴 common prefix의 길이라고 정의하자. 편의상 $z[0] = 0$이다. 이러한 $z$ 배열을 문자열 $s$의 Z-function이라고 부른다. 예를 들어, 문자열 "aaaaa"의 경우, $z = [0, 4, 3, 2, 1]$이 되며, 문자열 "aaabaab"의 경우, $z = [0, 2, 1, 0, 2, 1, 0]$이 되고, 문자열 "abacaba"의 경우, $z = [0, 0, 1, 0, 3, 0, 1]$이 된다. Z-function을 $O(n^2)$ 시간복잡도로 naive 하게 구하면 아래와 같이 코딩할 수 있다. vector z_functio..

Convex Hull Optimizaiton 중에 추가되는 직선의 기울기에 경향성이 없다면, 직선들을 스택으로 관리하지 못하고, set으로 관리하여 lower_bound 같은 연산을 잘 활용해주어 해결해야 한다. 그런데 이렇게 코딩하는 것은 여간 쉬운 일이 아니다. 실제로 Convex Hull Optimization을 사용하는 DP 문제는 아니지만, 이런 상황을 잘 표현해주는 예시 문제(반평면 땅따먹기)로 설명을 이어가겠다. 직선들을 set으로 관리하는 방법으로 위 문제를 해결하면 코드는 다음과 같이 되며, 꽤나 복잡하다. 더보기 #include using namespace std; #define MAXN 100005 typedef __int64_t lld; typedef __int128_t lll; i..