Eau de Cologne
문제: 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$개는 ..
문제: https://www.acmicpc.net/problem/25964 힌트: 더보기 이 문제에서 $N=K$인 경우, 구하는 수는 교란수 (https://en.wikipedia.org/wiki/Derangement)와 직접적인 관련이 있습니다. 풀이: 더보기 헨젤이 떨어뜨린 돌로 가능한 경우의 수는 $\frac{N!}{(N-K)!}$ 입니다. 이제 그레텔이 떨어뜨린 돌로 가능한 경우의 수를 구하기 위한 포함 배제 원리를 사용합시다. 헨젤과 그레텔의 돌 중 정해진 $i$개가 겹치는 경우의 수를 생각하면, 정해진 $i$개를 제외하고 나머지는 $N-i$개 중 $K-i$개를 고르는 경우의 수이기 때문에 $\frac{(N-i)!}{(N-K)!}$입니다. 정해진 $i$개를 고르는 방법은 $\binom{K}{i}..
문제: https://www.acmicpc.net/problem/7916 풀이: 더보기 일단 원점을 지나는 점이 생기도록 모든 백터에서 ${\vec v_0}$를 다 빼준 이후 버립시다. 이제, 명시적으로 모든 파리들이 존재하는 평면을 찾아봅시다. $\vec n = {\vec v_1} \times {\vec v_i}$ 가 $\vec{0}$ 이 아니면, 우리는 파리들이 존재하는 평면을 찾았습니다. 모든 $i$에 대해 $0$이라면, 모든 벡터가 한 직선 위에 있는 것이므로, TAK을 출력해 줍니다. 이제, 찾은 하나의 평면 위에 모든 파리가 다 존재하는지 확인합니다. $\vec n \cdot \vec {v_i}$가 모두 $0$인지 확인합니다. 구현: https://www.acmicpc.net/source/sh..