Eau de Cologne
문제: 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..
문제: https://www.acmicpc.net/problem/20123 풀이: 더보기 일단, $\frac{N(N+1)}{2}$가 $3$의 배수가 아니면 개수가 안 맞아서 채울 수 없습니다 이제 가능성은 $N \equiv 0, 2, 3, 5 \pmod 6$ 만 남았습니다. $N=0$: 빈 타일링입니다. $N=2$: 하나의 타일을 사용한 타일링입니다. $N=3, 5$: 타일링이 불가능합니다. (모서리를 먼저 채워보면 알 수 있습니다.) $N=9, 11$: 위와 같은 형식으로 타일링이 가능합니다. ($N=11$일 때는, 아래쪽 두 줄을 채워주면 됩니다) 이제 어떤 $N$층 계단의 타일링이 주어졌을 때 $N+6$의 타일링을 하는 법을 생각해 봅시다. $N+6$층 계단을 타일링 하는 법은, 위쪽 $6$층 계단..
문제: https://www.acmicpc.net/problem/12825 힌트 1: 더보기 $3-1-2$ free permutation과, (모든 $i$에 대해) "$A_1, \cdots, A_i$의 maximum을 $v$라고 했을 때, 이후 등장하는 $A_{i+1}, \cdots, A_N$ 에 등장하는 $v$ 미만의 수만 모으면 모두 내림차순으로 등장해야 한다"는 말은 동치입니다. 힌트 2: 더보기 임의의 수열에 관한 Next Permutation은 어떻게 구현할까요? https://en.cppreference.com/w/cpp/algorithm/next_permutation 를 참고합시다. 풀이: 더보기 "힌트 1"의 관찰을 사용하면, $A_1, \cdots, A_i$가 3-1-2 free perm..
문제: https://www.acmicpc.net/problem/15479 문제 요약: $A$의 연속된 부분수열 중 길이가 $K$ 이상인 모든 부분수열을 구하고, 그 수열의 (작은 순으로) $K$ 번째 수를 구합니다. 그 수를 모두 모았을 때 $L$ 번째 수를 구합니다. 풀이: 더보기 $A$의 모든 값이 $0$이나 $1$인 경우 $L$ 번째 수를 구하기 위해서는 $K$ 번째 수가 $0$인 구간의 수를 세면 됩니다. $K$ 번째 수가 $0$이라는 것은 수열에서 $0$이 $K$ 개 이상 있다는 의미입니다. 이는 two-pointer를 사용하면 쉽게 구할 수 있습니다. 원래 문제를 결정문제로 바꾸기 위해서 parametric search를 사용하면 문제를 해결할 수 있습니다. 코드: https://www.ac..
문제: https://www.acmicpc.net/problem/19669 풀이: 더보기 degree가 $1$인 노드 $u$를 생각합시다. 해당 노드에 소방서를 놓는 것과 해당 노드랑 바로 인접한 간선 $v$에 소방서를 놓는 것을 생각해보면, $u$를 제외한 다른 모든 정점은 $v$에 소방서를 놓는 것이 더 가깝습니다. 만약 $v$에 소방서를 놓은 이후 길이가 $w (\le K)$인 도로를 따라 $u$로 올 수 있다면, $u$에는 굳이 소방서를 놓을 필요가 없습니다. 이 경우에는 $v$와 $K-w$ 거리 이내에 있는 소방서가 있는 것으로 충분합니다. 이 관찰을 확장해서 정점 $i$가 거리 $R_i$ 이내의 소방서를 필요로 한다고 해 봅시다. degree가 $1$ 인 노드 $u$와 길이 $w$의 도로로 인..