Problem Solving Diary #20

D5 이상 랜덤 ICPC 문제 10개를 뽑았다.

3. Big Brother

반평면 교집합 기초 연습문제다. 어딘가에서 라이브러리를 긁어와서 풀었다.

7. Fair Distribution

$N=1$인 경우는 사전에 N을 출력하고 종료하는 식으로 처리해 주자. $N \ge 2$일 때를 생각해 보자. 각 빌딩의 높이를 $G_i + R_i x$ 꼴로 표현할 수 있다. $x$는 임의의 양의 정수가 될 수 있다. 그런데 모든 빌딩의 높이를 $lcm(R_1, \cdots, R_N)$의 배수만큼 올려놓고 생각할 수 있어서 사실상 $x$는 모든 정수라고 생각해도 문제없다.

 

일단 처음에 신경써야 할 것은 $gcd(R_1, R_2, \cdots, R_N)$의 값이다. 만약 배분한 $G$값의 합의 차이가 이 $gcd$ 값의 배수가 되지 않는다면 당연히 $x$들을 잘 맞춰서 균형을 잡는 것이 불가능할 것이다. 이제 이 조건을 만족하는 한은 항상 균형을 잡는 것이 가능하다는 것을 보이자. 이것은 어떤 양의 정수 수열 $(p_1, p_2, \cdots, p_n)$에 대해 $p_1 x_1 + p_2 x_2 + \cdots + p_n x_n = gcd(p_1, \cdots, p_n)$이 되는 정수 수열 $(x_1, x_s, \cdots, x_n)$이 항상 존재한다는 것으로 증명할 수 있다.

 

결국 관건은 $G_1, \cdots, G_N$을 두 묶음으로 나눠, 각 묶음의 합의 차이가 어떤 특정 수 $p$의 배수가 되게 할 수 있는지를 보는 것이다. 각 묶음의 합을 $A$와 $B$라고 해 보자. 모든 $G$의 합을 $S$라고 하면 $A+B=S$이다. 따라서 $A \equiv B \bmod p$, $A \equiv S-A \mod p$이므로 $S \equiv 2A \bmod p$여야 한다. $p$가 짝수이고 $S$가 홀수이면 불가능하고, 아니라면 $A$의 후보를 하나 또는 두 개 얻게 된다.

• $p$가 홀수라면 후보가 정확히 하나 나오게 된다.
• $p$가 짝수이면 항상 $S$는 후보가 둘 나온다. 예를 들어 $p=4$, $S=18$이면 $A=1$ 또는 $A=3$이다. 그런데 식을 정리해 보면 알겠지만 이 후보는 항상 $\frac{p}{2}$만큼 차이나서, 그냥 $p$를 반으로 줄이고 생각해도 상관없다.

이제 남은 것은 $G$ 값들의 집합에서 합을 $p$로 나눈 나머지가 $A$가 되는 집합이 있는지를 찾는 것이다. $p$로 나눈 나머지만 중요하므로 모든 수가 $p$ 미만이라고 가정해도 좋다. 그리고 합이 $2 \times 10^5$인 수들을 이용해서 냅색을 하면 되는데, 이건 $O(X \sqrt{X })$ 에 해결 가능한 꽤 유명한 문제이다. (https://www.acmicpc.net/problem/10008 참고) 이렇게 문제를 풀면 된다. 비트셋을 이용해서 풀 수도 있는 모양이다.

1. Falling Blocks

일단 의미 있는 칸은 아래 7줄, 각 줄당 3칸씩 $21$칸이다. 나머지 칸은 차는 순간 바로 게임이 종료되기 때문이다. 따라서 상태가 총 $2^{21}$가지 있다는 것을 알 수 있다.

 

또한 각 상태에서 블록마다 4가지 상태로 변할 수 있다. 4가지 방향으로 회전해 넣을 수 있기 때문이다. 각 방향으로 회전해 넣었을 때 어떤 상태로 변하는지를 시뮬레이션해야 한다. 따라서 시뮬레이션해야 하는 경우의 수가 총 $2^{21} \times 8 \times 4 = 2^{26}$가지이다. 벌써 거의 1억에 가깝기 때문에, 시뮬레이션을 빠르게 실행되도록 구현해야 한다. 또 한 가지 문제는 메모리 제한 대문에 $2^{26}$개의 정수를 저장할 수 없다는 것이다.

 

먼저 메모리 문제부터 보자. 실질적으로 우리에게 중요한 상태는 $2^{21}$개가 아니다. 한 줄이 꽉 찬 상태는 생각할 필요가 없으므로 $7^7$가지로 줄고, 이것은 앞의 $2^{21}$보다 반 이상 줄어든 수치이다. $7^7$과 $2^{21}$ 사이의 일대일대응을 만든 뒤, $7^7 \times 8 \times 4$짜리 상태 전이표를 만들면 메모리 제한에 걸리지 않는다. 이제 답을 구하기 위해서는 이 상태 전이표를 바탕으로 그래프를 만들고 순환해 주면 된다. 그래프에는 $(x, t)$ 쌍마다 정점 하나를 만들어 주면 되는데, $x$는 현재 상태이고 $7^7$ 미만이다. $t$는 현재 시각을 $n$으로 나눈 나머지를 의미한다. 이 그래프 위에서 사이클에 도달할 수 있으면 답은 forever일 것이다. 사이클에 도달할 수 없다면 그냥 일반적인 DP를 하듯이 게임이 끝날 때까지 최대한 버티는 시간을 구하면 된다.

 

시간 복잡도는 정말 이상하게 생겨서 딱히 적기 싫다. 구현 실수할 요소가 정말 많다.

9. How I Mathematician Wonder What You Are!

반평면 교집합 기초 연습문제 2. 앞 문제 코드 거의 복붙하고 몇 줄만 바꾸면 맞는다.

5. Quadrilaterals

옛날에 클래스 문제로 본 적 있었는데 포기했던 것 같다.

다음 개수를 셀 수 있어야 한다.

• 볼록사각형의 개수 (개당 2점)
• 오목사각형의 개수 (개당 1점)
• 최소 면적 $a$인 사각형의 개수 (개당 2점)

먼저 볼록/오목사각형의 개수부터 보자. 이들을 직접 세기는 조금 어려우므로, 다음의 개수를 셀 것이다.

• $P$의 네 점 $(A, B, C, D)$의 순서쌍의 수. 단, $A$는 삼각형 $BCD$ 내부에 있다. ($B, C, D$가 순서만 달라진 것은 하나로 생각)

위 개수를 세면 뭐가 좋을까? 일단 전체 순서쌍은 $n \times {}_{ n-1} C_3$개이다. 이 중 위 조건을 만족하는 순서쌍이 $P$개, 아닌 것이 $Q$개라고 하자. (당연히, $P$를 구하면 $Q$도 자동으로 나온다.) $P$에서 네 점을 골라 하나의 사각형을 만들 때, 이들은 네 가지 순서쌍에 대응한다. 만약 해당 사각형이 볼록사각형이면 네 순서쌍 모두 $P$에 들어갈 것이고, 오목사각형이라면 네 순서쌍 중 세 개는 $P$, 하나는 $Q$에 들어갈 것이다. 또한, 오목사각형의 경우 점의 집합은 그대로 두고 순서만 바꿔서 세 개의 사각형을 만들 수 있다. 결과적으로 다음이 성립한다.

• 볼록사각형의 개수: $\frac{1}{4} (P-3Q)$
• 오목사각형의 개수: $3Q$

그렇다면 이제 $P$와 $Q$를 구하는 방법을 알아보자. $P$를 구하는 게 훨씬 쉬운데, 각 점을 기준으로 다른 점들을 각도 정렬한 뒤 투 포인터를 돌려서 구하면 된다. $Q$는 단순히 전체 순서쌍 개수에서 $P$를 빼주면 된다.

 

다음으로 면적 $a$인 사각형의 개수를 살펴보자. $a$는 가능한 사각형의 최소 면적이다. 사각형은 두 대각선 중 하나가 무조건 사각형에 포함된다. 이 대각선을 고정하자. 넓이를 최소로 만들기 위해서는 대각선 양쪽의 점을 잡을 때, 대각선에서의 거리가 최소가 되도록 잡아야 한다. 문제 조건상 한 직선에 세 점이 있는 경우가 없으므로, 이런 점은 양쪽 각각 최대 두 개씩 존재한다. 이 점들을 빠르게 찾을 수 있다면, 이 점들로 만드는 볼록/오목사각형의 개수를 세어 답을 구할 수 있다. 이것은 Bulldozer Trick을 쓰면 쉽게 계산해줄 수 있다. 따라서 문제를 $O(N^2 \log N)$에 해결할 수 있다.

4. Kiwi Trees

제출하는 코드마다 계속 틀려서 에디토리얼을 보고 풀었다. 이런 류의 문제를 처음 봐서 신기하긴 했는데 그와 별개로 구현이 별로다.

 

대충 요약하면, $N \ge 4$인 경우 ear라는 것이 최소 두 개 존재한다. 여기서 ear는 다각형의 어떤 연속한 세 꼭짓점 $A_i, A_{i+1}, A_{i+2}$로 이루어진 삼각형 내에 다각형의 다른 꼭짓점이 포함되지 않은 것을 의미한다. 문제 각도 조건상 이 삼각형 내에 항상 원을 그릴 수 있으므로, ear 두 개에 적당히 원을 끼워 그리면 문제를 맞는다. $N=3$이면 두 변에 접하는 원 세 개를 후보로 넣고 가능한지 봐주면 된다.

2. Intrinsic Interval

Permutation Tree 기초 연습문제다. 난 이 자료구조를 몰라서 이 글을 보고 배워서 풀었다. 굉장히 흥미로운 구조인 것 같아서 나중에 정리해서 블로그에 올려보고 싶다는 생각이 들었다.

 

문제 특성상 Permutation Tree를 직접 구현할 필요는 없고, 그 과정만 이해하는 정도면 충분하다.

6. LCM Tree

에디토리얼을 보고 해결했다.

 

$n$이 조금 작다면 이 문제를 어떻게 풀 수 있을 지 생각해 보자. 일단 당연히도 비트마스킹을 이용한 DP로 해결해야 할 것이다.

 

먼저 수들을 내림차순으로 정렬한다. 이제 DP를 할 것인데, 현재 아직 리프 노드를 정하지 않은 정점들의 집합을 비트마스킹으로 관리할 것이다. 여기에는 리프 노드의 유무를 정하지 못한 것도 당연히 포함된다. 이제 이 정점 리스트에서 가장 큰 수 $x$를 아직 사용되지 않은 수 $y$와 $z$ 두 개를 골라 $lcm(y, z)$로 나타내거나, $x$를 리프 노드로 사용하는 선택 중 하나를 하며 DP를 진행할 것이다.

 

두 가지 부분이 조금 어렵다. 첫 번째 부분은 아직 사용되지 않은 수를 찾는 것인데, 항상 가장 큰 수 $x$부터 뽑는 DP의 특성상 $x$보다 큰 수는 모두 사용했을 것이라고 보아도 되고, $x$보다 작은 수들은 만약 사용되었다면 모두 비트가 켜져 있을 것이다. 따라서 $x$보다 작으면서 비트가 꺼져있는 수들이 그 후보가 될 것이다.

 

두 번째 부분은 같은 수를 처리하는 것이다. 이것을 잘 처리하기 위해, 만약 같은 종류의 수가 여러 개 남아있다면 그 중 맨 앞의 것을 고르도록 하면 된다. DP를 진행하며 만약 여러 개 남은 수를 고른다면 그 수의 가짓수만큼을 곱해 주면 된다. 단 같은 수를 두 개 고른다면 $2$로 나눠 줘야 한다.

 

시간 복잡도는 $O\left( 2^n n^2 \right)$이지만, 실제로 가능한 상태의 개수가 그리 크지 않은 등의 이유로 시간 내에 돈다고 한다.

나머지 문제들

시간 관계상 풀지 못한 문제들은 나중에 기회가 된다면 풀어볼 생각이다. 물론 두 문제 다 정말 풀기 싫게 생겼다.

• 8. Cornering At Poles
• 10. Polygonal Puzzle