취미로PS하는사람

https://www.acmicpc.net/problem/12876 일차함수 $y=a_ix+b_i$들의 최댓값에 대해 생각해보자. 잘 생각해보면, 최댓값을 이루는 직선들의 기울기는 $x$좌표가 증가하며 단조증가함을 알 수 있다. 만약 단조증가하지 않는다면, 기울기가 감소하게 된 직선의 이전의 직선이 더 큰 함수값을 가지므로 모순이 된다. 따라서, CHT를 짜듯이 된다. 다만 입력으로 들어오는 직선의 기울기의 단조성이 없고, 삽입과 삭제가 있다. 때문에 적당한 이분탐색과 set으로 직선들을 관리해야 한다. 하지만 우리에게는 더 무지성을 지향할 수 있는 자료구조가 있다. 바로 리차오 세그먼트 트리이다. 어떤 구간의 중앙값에서 가장 함숫값이 큰 함수에 대해 생각하자. 이를 그 구간을 대표하는 직선이라고 하자...

https://www.acmicpc.net/problem/17642 센트로이드 분할과 레이지 세그를 이용한다면 이론적으로는 풀 수 있다. 하지만 그걸 언제 구현하고 앉았는가... 오일러 투어 순서를 나열해보자. 그리고 그 사이에 간선의 가중치를, 내려갈 때는 +, 올라갈 때는 -로 생각해보면..? 정점 $x$와 정점 $y$사이의 경로는 오일러 투어 상에서 $x$가 맨 처음 등장하는 위치를 $s_x$라 할 때 대략 $s_{x}$~$s_{y}$의 구간의 가중치를 적당히 더하고 뺀 값과 같게 된다. 정확히는, 구간을 두 개로 쪼개 앞쪽은 모두 빼고 뒤쪽은 모두 더한 결과의 최댓값과 같게 된다. 그 이유는, 우선 실제 경로상에 포함되지 않는 경로의 경우 내려갔다와 올라갔다와 모두 포함되기 때문에 상쇄되어 0이 ..

https://www.acmicpc.net/problem/4149 큰 수를 소인수분해 해보자. 우선 밀러-라빈 알고리즘으로 해당 숫자가 소수인지 판별한 후 폴라드-로 알고리즘으로 소인수분해 하면 된다. 밀러-라빈 알고리즘은 검사하는 소수의 개수를 $k$, 소인수분해 하려는 수를 $n$이라 할 때 시간복잡도가 $O(k \log^3 {n})$이다. 자세한 사항은 위키백과를 참고하자. 참고로 $2^{64}$까지의 숫자를 결정론적으로 검사할 때는 $p = 2, 3, 5, ..., 37$이면 충분하다. 폴라드-로 알고리즘은 어떤 난수 발생 함수(이를테면 $f(x)=(x^2+1)\mod n$)가 $\mod n$에 대해 반복됨을 이용하는 것인데, 그 반복되는 주기가 $n$의 약수임을 이용한다. 자세한 내용은 나도 잘..