Eau de Cologne
문제: 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 < ..
문제: https://www.acmicpc.net/problem/14263 풀이: 더보기 어떤 한 카드의 원래 영역을 생각 해 봅시다. 이 영역은 직사각형 모양이기 때문에, 주어진 종류의 모든 색을 포함하는 직사각형 영역을 포함해야 한다는 것을 알 수 있습니다. 여기서는 이런 직사각형 영역중 최소한의 영역만 생각하면 됩니다. 직사각형 영역이 더 크다는 것은 더 많은 (불필요한) 제약조건을 의미하고, 우리는 가능한 모든 상태에서 사전순 최소를 찾아야하기 때문입니다. 이제 각 직사각형 영역에 대해서, 해당 직사각형 영역에 다른 색이 올라와 있다는 것은, 덮이는 순서가 정해져있다는 것입니다. 해당 직사각형 영역 다음에 다른 색이 덮여야 합니다. 이를 이용하면 어떤 두 색 간의 덮는 순서를 알 수 있습니다. (..
문제: https://www.acmicpc.net/problem/22011 관찰 1: 더보기 1번 세일은 항상 $3$개의 물건을 사는 것으로, 2번 세일은 항상 $1$개의 물건을 사는 것으로 생각해도 됩니다. 관찰 2: 더보기 1번 세일로 산 물건들은, 가격이 높은 것부터 정렬해서 $3$개씩 사는게 항상 이득입니다. 풀이: 더보기 정답이 존재하면 항상 관찰 1과 관찰 2의 조건들을 만족하면서 물건을 사는 방법이 존재하기 때문에, 해당 경우만 고려합니다. 물건을 가격의 내림차순으로 정렬한 후, 다음과 같은 상황을 생각해 봅시다: "$1$번 세일을 사용해 무료로 구매한 물건 중, 가장 가격이 높은 것은 $i$번째 물건이다." 이 경우에, $1, 2, \cdots, {i-1}$ 번째 중에서 정확히 $2$개는 ..