구사과

http://gall.dcinside.com/board/view/?id=rock&no=1734130&page=1

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할 수 있다.벌이 ..