3월 2주차 PS 정리

7문제, 대략적인 난이도 순. solved ac에 등록된 백준 문제들은 그 티어 순이고, Codeforces 문제는 대충 체감 난이도대로 넣었다. 체감 난이도다 보니 내가 잘 못푸는 스타일의 문제 난이도가 높게 평가되는것 같다. 

BOJ 04225, ICPC World Final 2011 K - Trash Removal

백준 번역명 "쓰레기 슈트"

난이도 : Platinum 3

다각형이 통과할 수 있는 가장 좁은 폭을 구하는 문제. 기하적인 관찰을 통해, 두 점 $A_i$ 와 $A_j$ 를 잡고 그 둘을 잇는 직선에 평행하게 들어가는 경우가 최선임을 알 수 있다. 즉, 그 직선에 수직인 직선 $L$을 잡고, $L$에 다각형의 모든 점을 정사영했을 때 가장 멀어지는 길이를 찾으면 된다. 예를 들어 y축에 평행하게 다각형을 집어넣고자 한다면 x축에 다각형 전체를 사영해서 얻어지는 가장 긴 직선을 찾는 식이다.

남은 구현은 고등학교때 풀었던 기하와 벡터 문제를 코딩하는 느낌...? 나는 꽤 힘들었다. 주어진 직선에 수직한 단위벡터를 구하는 식으로 구현했는데 축에 평행한 케이스도 있고... 하여튼 복잡하다. 

 

Codeforces Round 627 (Div.3) F - Maximum White Subtree

난이도 : Codeforces 

Codeforces 라운드 후기를 따로 적었다. DP가 약하기도 하고... 트리 DP 못해서 1시간이나 걸렸다. :(

[후기 / 풀이 링크]

BOJ 10846, Asia-Pacific Informatics Olympiad 2015 1 (APIO) - Bali Sculptures

백준 번역명 "발리의 조각상"

난이도 : Platinum 1

두가지 서로 다른 경우에 서로 다른 DP를 짜야 하는 문제. 기본적으로는, 어떤 Array를 연속한 $a$조각 이상 $b$조각 이하로 잘라서, 각 조각의 원소들의 합을 각각 구한 후, 그것들의 Bitwise OR 를 구한다. 이를 최소화하고 싶다.

전체 답에 대한 탐색을 하는데, 각 답을 비트별로 탐색하기로 하자. 즉, 높은 비트부터 보면서, 최종적인 답에서 $x$번째 비트를 끌 수 있다면 (즉, $x$번째 비트가 0인 답이 하나라도 존재할 수 있다면), 뒤에 무슨 일이 일어나든 그 비트를 끄는것이 반드시 이득이다 (아래 비트의 모든 값을 더해도 $x$번째 비트의 값보다 작으므로.) 따라서, 50번째 비트 (충분히 크게 잡자) 에서부터 아래로 0번째 비트까지 내려가면서, 어떻게든 끌 수 있는 비트가 있다면 끄고, 그렇지 않다면 켠 채로 다음 비트를 끌 수 있는지 확인한다.

각 비트의 확인은 기본적으로, dp 테이블을 채우는데, 그 비트를 켜지 않으면서 지금 숫자를 맨 끝 그룹에 넣으려면 어느 그룹에 넣어야 하는지를 dynamic programming을 통해 찾을 수 있다. (코드로 쓰면 좀 간단한데 말로 쓰면 너무 복잡하다. 코드를 참고하면 쉽게 이해할 수 있을 것 같다) $a = 1$ 인 경우 비교적 간단하게 1차원 DP, $a \neq 1$ 인 경우 2차원 DP를 해야 하므로 시간 복잡도는 $a = 1$ 인 경우 $O(bn^2)$, $n \leq 2000$ ($b$ 는 비트 수, 50이면 충분하다), $a \neq 1$ 인 경우 $O(bn^3), n \leq 100$ 이므로 둘 모두 충분하다. 

별개로 이렇게 두 경우를 아예 갈라서 함수를 두개 짜게 한 의도를 잘 모르겠다. $a \neq 1$ 이 훨씬 일반적인 경우고, $a = 1$ 인 경우에 복잡도를 내릴 수 있다는 사실을 알아야 만점을 받을 수 있는 문제라면 납득이 안 가는 것은 아니지만, 굳이? OI를 참여해 본 적이 아예 없다 보니 OI의 마인드는 어떤지...

코드 : https://www.acmicpc.net/source/share/a00ea30ac4cf495f84b6dd3bcf28d9b3

 

AtCoder Grand Contest 021 B - Holes

대충 문제를 설명하자면, 

1) 사실상 무한히 큰 공간에 점이 $n$ 개 존재한다.

2) 공간 어딘가에 점을 하나 찍어서, 처음에 찍은 점들 중 '가장 가까운 점' 을 찾는다.

3) 각 $n$개의 점이 '가장 가까운 점' 이 될 확률을 구해야 한다.

이 문제는 일단 Voronoi Diagram 에 관한 문제이다. 그러나, '바깥쪽 공간' 이 무한하기 때문에, Voronoi Diagram의 공간이 유한한 부분은 항상 확률이 0이 된다. 즉, 이 상황에서 Voronoi diagram을 그리면 바깥쪽을 향하는 부채꼴 비슷한 무한히 큰 공간들로 잘리게 된다.

부채꼴은 정확히는 가운데 부분이 뾰족하지 않고, 대충 잘려 있겠지만, 가운데 부분은 중요하지 않다. (어차피 바깥쪽 공간이 무한하기 때문에, 안쪽 모양은 확률적으로 0이므로) 

전체 도형의 Convex Hull을 구하고, Convex hull에서 인접한 점 $i-1, i, i+1$ 간의 각도를 $\theta$ 라고 하자. 이때, 그 점을 중심으로 뻗어나가는 부채꼴 형태 도형의 중심각이 $\frac{(\pi - \theta)}{2\pi}$ 임을 기하적으로 잘 관찰할 수 있다. Convex Hull 구현이 조금 귀찮지만 대충 라이브러리를 복붙해서 해결할 수 있다.  

 

BOJ 10919, International Olympiad of Informatics (IOI) 2015 1 - Boxes with Souvenirs

백준 번역명 "선물 상자". IOI 공식 번역명일텐데 왜 기념품 상자가 아닌지 잘 모르겠다. 본문도 전부 선물이다.

원형 공간을 돌면서 모든 팀에 선물을 배달해야 하는데, 이동 거리에 비례하는 시간이 걸리고, 한번에 $K$ 개 까지만 선물을 들고 움직일 수 있다. 

먼저, 선물을 '주는 경로' 만 생각하기로 하자. (돌아오는 경로는 일단 무시하고) 만약 선물을 주러 가는 모든 경로들을 원 위에 그렸을 때, 한 바퀴 넘게 전체 공간을 돌아야 한다면 반드시 이를 개선할 수 있다. 이유는, 만약 한 바퀴를 넘게 원을 돈다면 (시계방향으로 좀 돌고, 반시계방향으로 좀 돌아서 저기 어딘가에서 두 경로가 겹친다면) 그 구간을 한번만 도는 방법으로 이를 개선할 방법이 반드시 존재하기 때문이다. 

즉, 시계방향 순서대로 점을 쭉 나열한 후, 이를 돌면서 $m$개는 시계 방향으로, $n-m$개는 반시계 방향으로 돌면서 주는 것이 최선임을 알 수 있다. 이를 고려하는데, 시계방향으로만 도는 DP 테이블과 반시계방향으로만 도는 DP 테이블을 따로 관리하면 쉽게 해결할 수 있다.

선물을 $k$개 주고 나면 반드시 돌아가야 하고, $k$개보다 덜 들고 나오는건 상식적으로 뭔가 손해 볼거 같으므로 항상 $\texttt{dp[i-k]}$ 만 보면서 갱신하면 된다. 따라서, $O(n)$ 에 모든 경우를 갱신할 수 있고, $O(n)$ 에 $m$을 돌면서 최적값을 찾아낼 수 있으므로 Overall $O(n)$ 에 해결할 수 있다.

몇가지 케이스 (선물을 다 준 다음 거꾸로 돌아가는 대신, 그냥 앞으로 쭉 가서 0으로 돌아가는게 이득일 수도 있다) 만 고려하면 어렵지 않게 코딩할 수 있다. 

IOI 문제들 중 문제가 가장 덜 무섭게 생겨서 (...) 풀어봤는데, 확실히 코딩량이 적은것 같다. 특히, $n = 1e7$ 이라서 반드시 $O(n)$ 풀이가 있다는 너무 큰 힌트가 있다. 딱히 $O(n \log n)$ 풀이가 있어서 이를 잘라야 하는게 아닌데 일부러 힌트로 크게 준건가 싶기도 하고... 입력이 1000만 개의 정수가 들어오면 일부 언어들은 꽤 힘들 것 같다.

 

BOJ 13949, Central European Regional Contest (CERC) 2016 E - Easy Equation

백준 번역명 "쉬운 문제"

난이도 : Diamond 2

$a^2+b^2+c^2 = k(ab+bc+ca)+1$ 식을 만족하는 $a, b, c$ 순서쌍을 $n$개 찾아야 하는 문제. 각 순서쌍에 있는 숫자가 하나도 겹쳐서는 안 된다.

이러한 순서쌍이 무한히 존재함이 보장되는데, 적당히 많이 찾기 위해서는 다음과 같은 방법을 생각할 수 있다. 

$(0, 1, k)$ 에서 시작하자. 이는 유효한 답은 아니지만 (유효한 답은 $a, b, c > 0$ 이어야 하고, 겹치는 수도 쓰지 않아야 한다. 유효한 답인지는 매번 검사하기 어렵지 않다) 좋은 시작점이다.

Claim. $(a, b, c)$ 가 답이라면, $(kb+kc-a, b, c)$ 가 올바른 답이다. (유효한지는 일단 무시하자) 

Proof. 좌변에 새로운 답을 대입하면 $$(kb+kc-a)^2+b^2+c^2 = k^2(b+c)^2-2kab-2kac+a^2+b^2+c^2$$

우변에도 새로운 답을 대입하여,

$$k(kb+kc-a)(b+c)+kbc+1 = k^2(b+c)^2-kab-kac+kbc+1$$ 이다. $a^2+b^2+c^2 = k(ab+bc+ca)+1$ 에서, 좌우변이 같음을 얻는다.

같은 원리로 $(a, ka+kc-b, c)$ 와 $(a, b, ka+kb-c)$ 도 올바른 답이 된다. 이제, $(0, 1, k)$ 부터 시작해서 BFS로 전체를 탐색하면서 답의 후보를 발견할 때마다 올바른지를 확인하면 된다. 올바른지를 확인하기 위해서는 set 같은 자료구조를 적당히 쓰면 되고...

100자리라서 딱 쎄하겠지만, Big Integer를 구현하거나 파이썬을 써야 하는 문제다. 내 코드는 Python3로 제출하면 백준에서 264ms, PyPy로는 676ms 정도 걸리던데 보통은 PyPy가 빠른데 왜 그냥 파이썬이 더 빠른지는 모르겠다. 

 

BOJ 17441, 서울대학교 SNUPC 2019 Div1G - 파리채 만들기

난이도 : Diamond 2

다각형에서 임의의 두 점 사이의 거리의 기댓값을 구하는 문제. 중적분을 통해 구할 수 있다.

중적분 식을 직접 쓰고 나면 컴퓨터로 계산하는 것은 어렵지 않지만, 식 쓰는게 너무 어렵다. 수및연 II 를 Radioactive Island 이후로 또 펴 볼줄은 몰랐지... 

적분식을 열심히 정리해 보면, 구체적으로는 다음 식을 Evaluate 하는 문제가 된다. $S$는 다각형의 넓이.

$$\frac{1}{S^2}\left(\iint_D \iint_D (x_1-x_2)^2+(y_1-y_2)^2 \ dx_1\  dx_2\ dy_1\ dy_2\right)$$ 

$\displaystyle \iint_D x^2$ 같은 값은 그린 정리를 이용, $\displaystyle\int_{\partial D} \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \ dx \ dy$ 로 바꾸어 계산할 수 있다. 

SNUPC Div1은 너무 미친문제가 많은것 같다 : (