Eau de Cologne

문제: https://www.acmicpc.net/problem/18621 풀이: 더보기 일단 가장 간단한 문제의 성질을 이용한 hill-climbing 풀이를 생각합시다. 한 점을 잡고, 매 번 주위 8칸을 보면서 더 큰 쪽으로 이동합니다. 이 방법으로 답을 찾을 수 있다는 것은 간단하지만 매우 중요하게 사용될 것입니다. 답이 있는 영역을 절반으로 줄여봅시다. $(\left\lceil N/2 \right \rceil, *)$ 위치에 대해 쿼리를 날린 이후, 해당 가로줄에 있는 수중 가장 큰 수가 있는 위치 $(\left\lceil N/2 \right \rceil, j)$ 근처의 모든 셀에 대해 쿼리를 날립니다. $(\left\lceil N/2 \right \rceil, j)$보다 큰 수가 없을 경우에는..

문제: https://www.acmicpc.net/problem/10513 풀이: 더보기 거리가 가장 먼 것 부터 터트리는 것을 생각합시다. 해당 우주선을 $t$ 시간에 터트리면 해당 $t$ 시간이 포함되는 모든 우주선은 같이 터지게 됩니다. 즉, $t$ 시간이 배제된 ($t$ 시간 이전에 없어지거나 $t$ 시간 이후에 나타나는) 우주선만 고려하면 되고, 이 두 우주선은 따로 고려할 수 있습니다. $D_{a, b}$를 $[a, b)$ 시간에 완전히 포함되는 우주선만을 처치하는데 드는 최소 비용이라고 합시다. ($a-1$ 시간과 $b$ 시간에 폭탄을 터트린 경우입니다. 가장 먼 거리의 우주선이 $[l, r)$ 시간에 있고, 거리가 $d$ 라고 하면 $D_{a, b} = \max_{l \le i < r} (..

문제: https://www.acmicpc.net/problem/7987 / https://www.acmicpc.net/problem/10542 풀이 (7987): 더보기 indegree가 0인 정점 $d$와 $d$가 가리키는 $a_d$가 모두 선택되지 않은 답이 있으면, $a_{a_d}$를 선택하지 않고 $a_d$를 선택하는 것으로 답을 옮길 수 있습니다. 이후에 $d$와 $a_d$는 그래프의 다른 성분에 영향을 미치지 않으므로 제거해도 됩니다. 즉, $d$와 $a_d$를 찾아서 아무거나 제거하는 것을 반복하면 스파이를 최적의 방법으로 배치할 수 있습니다. 이제 indegree가 0인 정점이 없는 사이클인 경우만 남고, 각 사이클의 길이를 $C$라고 하면 $\left\lfloor C/2 \right\r..

에라토스테네스의 체에서 간단한 최적화만으로도 매우 빠르게 동작합니다. $O(N \log \log N)$ 시간복잡도를 가졌지만, 로컬에서 1억에 0.25초, 10억에 3.6초 정도에 동작합니다. HTML 삽입 미리보기할 수 없는 소스 기본적인 에라토스테네스의 체와 같은 방식으로 처리합니다. 단, 다음과 같은 최적화를 거쳐줍니다. 1번 줄: vector은 필수적입니다. 라이브러리가 bit단위로 값을 저장하기 때문에, 메모리 사용량을 획기적으로 줄일 수 있습니다. (수 800만개당 1MB입니다. 1억은 12.5MB, 10억은 125MB를 사용합니다) 2-4번 줄: 소수가 될 수 있는 수는, 3 이상의 홀수와 2 뿐입니다. 5번 줄 (i=3, i+=2): 2의 배수는 이미 불가능하다고 체크했기 때문에, 3이상의..

문제: https://www.acmicpc.net/problem/16311 풀이: 더보기 현재 $u$번째 노드에 있다고 할 때; 좌뇌, 우뇌가 시작해서 $t$까지 가는 거리를 각각 $L_u, R_u$라고 합시다. 게임이론을 사용하면, 좌뇌는 가장 멀리 가고 싶어하고 우뇌는 가장 가까이 가고싶어하기 때문에 다음 점화식이 성립합니다: $L_t = 0, L_u = \max_{u \xrightarrow{w} v} {R_v + w}$ $R_t = 0, R_u = \min_{u \xrightarrow{w} v} {L_v + w}$ 여기서 무한루프를 고려하기 위해, $\infty$ 라는 특수한 값을 고려합니다. $r \in \mathbb R$에 대해 $r < \infty$이고, $\infty = r + \infty$..

문제: https://www.acmicpc.net/problem/23036 풀이: 더보기 $i$번 초과 $j$번 이하에 해당하는 페이지의 책을 골랐다고 합시다. 이 경우, $A_{i+1} + \cdots + A_j \ge P(j-i)$ 에 해당하는 $i, j$를 만족하는 인덱스의 개수를 세는 문제가 됩니다. $A_i-P$를 $B_i$라고 하면, $B_{i+1} + \cdots + B_j \ge 0$에 해당하는 $i, j$를 찾는 문제가 되고, $S_i = B_1 + B_2 + \cdots + B_i$ 라고 하면 $S_j - S_i \ge 0$에 해당하는 $i, j$를 찾는 문제가 됩니다. 즉, $S_0 = 0, S_i = S_{i-1} + (A_i - P)$ 로 $S$를 정의할 때, $0 \le i < ..