GCJ 2018 Qual Round 풀이 & 후기

새로 바뀐 플랫폼에서 처음 열린 Google Code Jam 2018의 첫 라운드인 Qualification Round가 끝이 났습니다. 다 맞은 기념으로 제 풀이와 후기를 써보았습니다. 구코잼 측 Analysis도 있습니다.

Saving The Universe Again

외계 로봇이 우주를 위협하고 있습니다. 외계 로봇은 C(charge)와 S(shoot) 두가지로 이루어진 명령을 수행합니다. 우리는 데미지 $D$를 막을 수 있는 보호막이 있고 로봇을 해킹해서 인접한 두 명령의 순서를 바꾸는 일을 할 수 있습니다. 로봇이 쏘는 빔의 공격력은 초기에는 1이고, C가 나오면 공격력이 2배가 되며, S가 나오면 빔을 쏘고 공격력은 유지됩니다. 최소한의 해킹으로 총 데미지를 $D$ 이하로 만들어야 합니다.

인접한 두개의 명령의 순서를 바꿀 수 있으므로 CSSC로 바꾸거나 SCCS로 바꿀 수 있는데 CSSC로 바꿔야만 총 데미지가 줄어듭니다. 또한 공격력이 두배씩 늘어나기 때문에 뒤에 수행하는 C에서 늘어나는 공격력이 더 큽니다. 따라서 가능한 한 뒤에 있는 CSSC로 바꾸는게 좋습니다.

명령의 길이가 $2 \le P \le 30$ 입니다. 데미지를 $O(P)$에 구하고 가장 뒤에 있는 CSSC로 바꾸는데 $O(P)$가 걸리도록 하였고 최대 swap 횟수는 약 $P^2/4$ 이므로 $O(P^3)$ 에 해결하였습니다.

Trouble Sort

연구실에서 띠용한 정렬 알고리즘을 만들었다고 합니다. 이름은 ‘triplet bubble sort’, 줄여서 ‘Trouble Sort’ 입니다. 이름부터 불안한 느낌이 납니다.

Trouble Sort는 bubble sort와 비슷하지만 인접한 2개의 원소를 보는게 아니라 3개를 보고 양 끝값을 비교하여 왼쪽이 오른쪽보다 크면 3개 전체를 뒤집습니다. 여기서 중요한건 3개의 원소 중 가운데 값은 위치가 변하지 않습니다. 즉, 홀수 번째 원소들은 홀수 번째 원소끼리 비교하고 swap하게 됩니다. 짝수 번째도 마찬가지 입니다. 따라서 Trouble Sort를 수행하고 나면 홀수 번째 원소끼리 정렬되고 짝수 번째 원소끼리 정렬된다는 걸 알 수 있습니다.

구하고자 하는 것은 Trouble Sort를 수행하고 난 뒤 처음으로 정렬이 안 된 부분의 인덱스 입니다.

Test set 1에서 $3 \le N \le 100$ 이므로 $O(n^2)$ Trouble Sort 알고리즘을 직접 수행할 수 있습니다.

Test set 2에서 $3 \le N \le 10^5$ 이므로 홀수 번째, 짝수 번째를 따로 정렬하면 $O(n\log n)$ 에 해결할 수 있습니다.

Go, Gopher!

$1000 \times 1000$ 크기의 과수원을 가꾸고 싶습니다. AVL, binary, red-black, splay 등의 나무를 심는다고 합니다. (…) 목표는 최소 $A$ 크기의 직사각형 모양의 칸들에 구멍을 파는 것입니다. 하지만 우리가 직접 삽질하기에는 너무 힘들기 때문에 Go 팀에서 gopher를 고용했습니다.

우리는 gopher에게 $(x, y)$ 좌표에 구멍을 파라는 명령을 보낼 수 있습니다. 하지만 gopher가 훈련이 덜 되었기 때문에 $(x, y)$에 명령을 보내면 $(x\pm1, y\pm1)$ 까지의 9개의 칸들 중 랜덤하게 한 곳을 팝니다. 명령을 너무 많이 보내면 gopher도 힘들기 때문에 최대 1000번 까지 명령을 보낼 수 있습니다.

인터렉티브 문제인데다가 랜덤이라니 너무나 불만이 많지만 우리는 로또를 연속으로 세번 맞을 운명이 아니기 때문에 문제를 해결 할 수 있습니다.

명령을 이곳저곳 보내면 확률을 예측하기 어려워지고 또한 비효율적이므로 9칸 단위로 구멍을 파기로 합시다. $(x\pm1, y\pm1)$ 의 9칸을 모두 팔 때 필요한 명령 수의 기댓값은 $\sum\limits_{i=1}^9 \frac{9}{i} = \frac{9}{1} + \frac{9}{2} + … + \frac{9}{9} \approx 25.5$ 입니다.

Test set 1에서 $A = 20$ 이므로 9칸씩 3번 반복하면 약 76회가 기대되고

Test set 2에서 $A = 200$ 이므로 9칸씩 23번 반복하면 약 586회가 기대됩니다.

Test set 2에서 실패할 확률을 대강 계산해보면, 586회를 사용해서 거의 다 팠지만 딱 한칸만 남았을 때, 남은 414회를 모두 실패 할 확률은 $(\frac{8}{9})^{414} \approx 6.65 \times 10^{-22}$ 로 로또 세번 맞을 확률인 $1.85 \times 10^{-21}$ 보다 낮습니다. 따라서 이 풀이로 틀렸다면 로또를 사보거나, 아니면 인공위성이 내 머리위로 떨어지지 않을까 하는 걱정도 해보는 것이 좋습니다.

Cubic UFO

외계비행선이 나타났습니다! 외계비행선은 한변의 길이가 $1km$인 3차원 큐브 모양이군요. 중심은 정확히 원점에 있고 비행선 아래 지면에는 그림자가 깔려 있습니다. 뜬금없는 외계비행선이지만 군은 만약 비행선의 그림자가 거의 정확히 $A km^2$ 이면 가만히 있겠다고 합니다. 비행선의 모양은 바꿀 수 없으므로 이리저리 잘 돌려서 그림자의 넓이를 맞춰야 합니다. $x$, $z$축이 지면과 평행하고 $y$축이 지면과 수직합니다.

우선, 각 면의 중심이 축을 지나도록 하면 위, 아래면이 지면과 평행하므로 그림자의 넓이가 $1km^2$ 입니다. 이 때 x축을 기준으로 조금씩 돌려봅시다. 넓이가 증가하다가 $45^\circ (=\frac{\pi}{4})$ 돌렸을때 최대로 $\sqrt 2 km^2$ 이 됩니다. $\theta$ 만큼 돌렸을 때 그림자의 넓이를 계산해보면 $\sin \theta + \cos \theta = \sqrt 2 \sin(\theta + \frac{\pi}{4})$ 로 $0$에서 $\frac{\pi}{4}$까지 단조증가 하네요. $A$가 $\sqrt 2$ 보다 작다면 저 식을 통해 $\theta$를 구할 수 있습니다.

이제 $x$축을 기준으로 $45^\circ$ 돌린 상태에서 z축을 기준으로 돌려봅니다. 계산과정은 귀찮으니 생략하고 $\theta$만큼 돌렸을 때 그림자의 넓이가 $\sin \theta + \sqrt 2 \cos \theta = \sqrt 3 \sin(\theta + \alpha)$ 가 됩니다. 이 때 최댓값이 $\sqrt 3 km^2$ 인 것도 알 수 있습니다.

Test set 1에서 $ 1 \le A \le \sqrt 2$ 이므로 $x$축만 돌려서 해결할 수 있습니다.

Test set 2에서 $1 \le A \le \sqrt 3$ 이므로 $z$축을 돌려서 해결해야 합니다.

저는 직접 계산하여 상수시간에 해결하였지만 적절한 각도로 잘 돌려서 이분탐색을 쓰는것이 문제를 푸는데는 더 빠를 수도 있겠습니다.

한 편, $n$차원 초입방체를 초평면에 정사영시켰을 때 최대 넓이가 $\sqrt n$ 일지 궁금해지기도 합니다.

후기

이번 GCJ 2018은 이전과 다른 새로운 디자인의 플랫폼에서 진행되고 있습니다. interactive 문제가 생기고 이 때문인지 제출 방식이 소스코드 + 아웃풋 제출에서 지정된 언어의 소스코드만 제출하도록 바뀌었습니다.
하지만 새로운 플랫폼에 친구 스코어보드, 다른 사람 소스 다운로드 등이 아직 미구현 상태인데다가 대회 중에 서버 응답이 매우 느려지는 이슈까지 발생하여 실망이 큰 상태입니다. 27시간 동안 진행된 Qual라운드와 다르게 R1에는 짧은시간동안 많은 사람이 참가할텐데 서버문제가 해결될지 걱정입니다.

공유하기