구사과

http://geniusainta.com/problems/view/APIO14_palindrome 이 문제의 정해는 Manacher's Algorithm + Suffix Array이다.난 전자는 알지만 후자는 모르기 때문에 (...) SA 대신 Hash를 사용해서 풀었다. 때문에 처음부터 해시를 사용했다는 가정 하에 설명한다. unordered_map을 기준으로 설명한다 (괜히 로그떼면 기분 좋으니까 (?)) 1. Naive - O(n^2)substring의 개수가 O(n^2)이며 해싱을 사용하면 팰린드롬 판별은 O(1)에 가능하다. 모든 팰린드롬을 map에 때려박고 개수를 세면 된다. 2. Hash + Manacher + Tree - O(n)일단 한 문자열의 서로 다른 팰린드롬의 개수는 n개임을 알고 ..

https://www.acmicpc.net/problem/5465 격자상에 어떠한 점도 Mecho가 일찍 도착하는 것이 무조건 이득이라는 점을 쉽게 관찰할 수 있다.이는 Mecho가 t만큼 꿀을 빨고 출발했을 때 도착할 수 있다면, t보다 작거나 같은 시간 u만큼 꿀을 빨고 출발해도 항상 도착할 수 있다는 것을 의미한다. 때문에 t의 정의역을 설정해 준 후 Parametric Search를 해주면 문제를 쉽게 풀 수 있다.이제 과제는 시간 t만큼 꿀을 빤 이후에 Mecho가 집에 도착할 수 있는지에 대한 문제로 귀결된다. 먼저, 벌들의 위치를 한꺼번에 Queue에 넣은 다음에 너비 우선 탐색을 할 경우, 한 격자에 도달하기까지 벌이 걸리는 시간을 쉽게 O(n^2) 에 precompute할 수 있다.벌이 ..

http://koistudy.net/?mid=prob_page&NO=593 1. Naive ( O(N^2lgN) ) 트리에 대한 기본적인 지식이 있으면 풀 수 있다. 서브트리의 경우의 수가 N개이니, N개의 각 경우에 대해서 내부에 있는 노드를 Greedy하게 더해서 경비병을 최대화 하면 된다.내부 노드에 있는 cost들을 그때 그때 sort해주면 N^2lgN이다. 2. Naive (...) ( O(Nlg^2N) ) 일단 그때 그때 sort해주기 보다는 priority_queue 등의 자료구조를 사용해서 서브트리에 있는 원소들을 재귀적으로 합쳐주자.이 역시 O(N^2lgN)이 걸린다. 이 때 합치는 대상이 되는 힙을 "가장 원소 개수가 많은 힙" 으로 설정해주자.약간의 커팅.... 은 무슨, 이걸로 시간..