Eau de Cologne
문제: https://www.acmicpc.net/problem/5477 풀이: 전반 더보기 우선, 무조건 제거되어야 하는 간선들을 찾아줍니다. 간선 $(u, v, w)$에 대해 트리에서 $u \rightarrow v$ 경로의 길이가 홀수이면, $(u, v, w)$와 트리 경로만 이용해서 짝수 사이클을 만들 수 있습니다. 그렇기 때문에 무조건 삭제되어야 합니다. 이제, 짝수 사이클이 만들어지는 조건을 찾아봅시다. $(u_1, v_1, w_1)$ 간선이 트리를 통해 만드는 사이클과, $(u_2, v_2, w_2)$ 간선이 트리를 통해 만드는 사이클은 모두 홀수 사이클입니다. 이제 두 사이클을 XOR하면 (즉, 간선 중 둘 중 한 쪽에만 포함된 간선을 찾아서 새로운 그래프를 만들면), 새로운 그래프는 사이클..
문제: https://www.acmicpc.net/problem/17146 힌트 1 (Subtask 1): 더보기 $D_{i, j} = 1$ 인 두 $i, j$ 정점들을 모두 합치고 (같은 색으로 칠해주고) 나면, 모든 $i \ne j$에 대해 $D_{i, j} = 2$가 됩니다. 이 경우에는 색을 번갈아가면서 칠하면서 문제를 해결할 수 있습니다. 트리의 모양은 아무렇게나 정해도 상관 없습니다. 힌트 2 (Subtask 2): 더보기 $1, \cdots, N-1$ 까지의 색을 정했을 때 $N$의 색을 정한다고 해 봅시다. $i$에서 $N$까지 가는 경로 위에 있는 정점의 색 집합은 $i$에서 $N-1$까지 정점의 색 집합에다가 $N$의 색을 추가한 것입니다. 만약 $D_{i, N} \ne D_{i, N-..
문제: https://www.acmicpc.net/problem/20662 힌트 1: 더보기 모든 $i r_1$, 초록색이면 $g_2 > g_1$, 파란색이면 $b_2 > b_1$을 만족해야합니다. 수가 증가하는 방향으로 간선을 긋는 것이 좋을 것 같으니, $0$부터 $N-1$까지의 수를 $4$진법으로 표현해봅시다. $r_2 \times 4^2 + g_2 \times 4^1 + b_2 \times 4^0 > r_1 \times 4^2 + g_1 \times 4^1 + b_1 \times 4^0$를 만족한다는 의미는, $r_2 > r_1$, $g_2 > g_1$, $b_2 > b_1$ 중 하나 이상을 만족한다는 의미입니다. 만족하는 색을 이용해서 간선을 그리면 간선의 할당에 따른 DP값이 올바르게 할당이 ..
문제: 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..