Eau de Cologne

문제: 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..

문제: 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..