GCJ 2018 R1A 풀이 & 후기

Google code Jam 2018 Round 1의 첫번째 sub-round 입니다.

Waffle Choppers

문제

동그란 팬케잌에 질린 요리사가 새로운 메뉴인 와플을 만들기로 했습니다! 이 와플은 $R \times C $ 크기의 격자모양이고 각 칸에는 초콜릿이 하나 있거나 비어있습니다.

이 와플을 가로로 정확히 $H$번, 세로로 정확히 $V$번 잘라서 $(H+1) \times (V+1)$ 개의 조각으로 만들어 사람들에게 나누어 주려고 합니다. 그런데 이 와플의 핵심은 크기가 아닌 초콜릿이기 때문에 잘라진 각 와플조각에 들어있는 초콜릿 개수가 모두 같아야 합니다. 이 때 이렇게 자르는 것이 가능한지 여부를 알고싶습니다.

풀이

먼저, 모든 와플조각에 있는 초콜릿 수가 같아야 하기 때문에 전체 초콜릿 수 $Total$ 은 $0$ 또는 $(H+1) \times (V+1)$ 의 배수여야 합니다. $0$개인 경우는 어떻게 잘라도 모두 0개이기 때문에 항상 가능합니다.

그 다음, 가로로 자르는 것을 생각해보면 자른 후 각 가로줄의 초콜릿 합이 결정됩니다. 한 줄에 정확히 $Total / (H+1)$ 개가 들어가도록 잘라야 합니다. 세로줄로 자르는 경우 또한 각 세로줄에 $Total / (V+1)$ 개가 들어가도록 잘라야 합니다. 즉, 가로/세로로 자르는 방법이 결정됩니다. 간혹 한 줄에 초콜릿이 하나도 없는 경우 자르는 경우의 수는 여러가지가 될 수 있지만 그럴 경우 어떤 방법이든 각 조각의 초콜릿 수는 변하지 않기 때문에 아무렇게나 잘라도 됩니다.

자르는 방법은 결정이 되었지만 각 조각에 같은 개수의 초콜릿이 들어갔는지는 알 수 없습니다. 각 조각에 $Total / ((H+1) \times (V+1))$ 개의 초콜릿이 들어있는지 확인합니다. 하나라도 다르면 불가능한 경우 입니다.

와플에서 임의의 직사각형 모양의 칸에 들어있는 초콜릿 개수를 빠르게 세기위해 2D Partial sum을 이용했습니다.

Test set 1

$H = 1, V = 1$ 이므로 자르는 모든 $(R-1) \times (C-1)$ 가지의 경우를 시도해볼 수 있습니다. 이 경우 $O(RC)$ 에 해결할 수 있습니다. $R \le 10, C \le 10$ 이기 때문에 2D Partial sum을 안 써도 $O(R^2C^2)$ 에 해결 가능합니다.

Test set 2

$R \le 100, C \le 100$ 이므로 위 방법대로 하면 $O(RC)$ 에 해결할 수 있습니다.

Bit Party

문제

Toronto에서 열리는 World Final에 필요한 물건들을 조달하기 위해 $R$ 개의 로봇을 배치하여 슈퍼마켓에서 총 $B$ 개의 ‘bit’를 사오도록 시키기로 했습니다. 지금은 AI 개선이 되어있지 않아서 우리가 직접 로봇들이 가능한 한 빠르게 사오도록 도와주려고 합니다.

슈퍼마켓에는 총 $C$ 명의 계산원이 있고 $i$ 번째 계산원은 한 고객당 최대 $M_i$개의 물건을 계산할 수 있고 각 물건을 계산할 때 마다 $S_i$의 시간이 들고 결제와 포장등으로 $P_i$의 시간이 듭니다. 즉 $n$ 개의 물건을 들고온 고객은 총 $S_i \times n + P_i$ 의 시간이 듭니다. ($n \le M_i$)

로봇이 계산원에게 계산을 맡기기 전에 우리는 각 로봇들에게 bit를 분배하고 어떤 계산원에게 계산을 맡길지 정해줄 것입니다. 다만 0개의 bit를 분배받은 로봇은 실망하여 계산원에게 가지 않고 바로 떠날 것입니다. 또한 각 로봇은 모두 각각 다른 한 계산원에게 한 번만 계산을 맡겨야 합니다. 모든 계산은 정확히 시간 0에서 시작합니다.

이 때 모든 로봇이 계산을 마쳤을 때의 가능한 한 가장 빠른 시간을 알고싶습니다.

풀이

가장 빠른 시간 안에 끝나도록 배치하는 방법을 바로 찾는 것은 어렵습니다. 하지만 특정 시간 안에 각 계산원이 몇개의 bit를 계산할 수 있는지 세는 것은 쉽습니다. 따라서 Parametric search (이분탐색) 기법을 활용합니다.

특정한 시간 $T$ 안에 로봇들이 $B$개의 bit를 계산할 수 있는지 판단해봅시다. 각 계산원마다 $b$개의 bit를 계산할 때 $P_i + S_i * b$ 의 시간이 소요되므로 각 계산원이 $T$ 시간 안에 계산할 수 있는 bit의 최댓값은 $b_{max} = floor(max(T-P_i, 0) / S_i)$ 입니다.

하지만 우리는 로봇이 $R$개 밖에 없으므로 $C$ 명의 계산원 중에서 가장 많이 계산할 수 있는 $R$ 명을 골라야 합니다. 그 $R$ 명이 계산할 수 있는 bit 수가 $T$ 시간 안에 계산할 수 있는 bit 수 입니다. 이 값이 $B$보다 크거나 같으면 $T$ 시간 안에 로봇이 계산을 마칠 수 있습니다.

이제 이분탐색으로 가능한 가장 작은 $T$ 값을 알아내면 됩니다. $T$ 값의 최댓값은 $max(M_i \times S_i +P_i) = 10^{18} + 10^9$ 임에 유의합니다.

Test set 1

  • $1 \le R \le C \le 5$
  • $1 \le B \le 20$

모든 경우를 brute force로 시도하는 것이 가능합니다.

Test set 2

  • $1 \le R \le C \le 1000$
  • $1 \le B \le 10^9$

위 풀이법대로 하면 $O(\log (min(B, M) \times S+P) \times C \log C)$ 에 해결할 수 있습니다.

Edgy Baking

문제

한 제빵사가 $N$개의 쿠키를 굽기 위해 반죽을 하였습니다. 각 쿠키는 $W_i \times H_i$ 크기의 직사각형 모양입니다. 쿠키를 오븐에 넣기 직전에 쿠키의 가장자리가 아주 맛있다는 것을 떠올리고 모든 쿠키의 둘레의 길이 합을 최대한 $P$ 에 가깝게 만들기로 했습니다.

각 쿠키마다, 쿠키를 정확히 절반의 넓이의 두 조각으로 자를지 말지 결정해야 합니다.(직사각형이 아니어도 됨) 잘라진 두개의 조각은 더 이상 자를 수 없습니다.

둘레의 길이 합을 $P$를 넘지 않으면서 최대한 $P$에 가깝게 했을 때의 둘레의 길이를 알고싶습니다.

풀이

먼저, 각 쿠키를 자를 때 늘어나는 둘레 길이의 구간은 최소 $L_i = 2 \times min(W_i, H_i)$, 최대 $R_i = 2 \times \sqrt{W_i^2 + H_i^2}$ 이고 사이값도 모두 가능하므로 $[L_i, R_i]$ 입니다. 이 때 쿠키들을 자르거나 자르지 않을 때 가능한 둘레의 합의 구간들을 모두 구해봅시다. 그 전에, $P’ = P - 2 \times \sum (W_i + H_i)$ 로 두어 늘어나는 둘레의 길이만 생각하도록 합니다.

$1 \le N \le 100$ 이기 때문에다 각 쿠키를 자르거나 자르지 않는 $2^N$가지의 모든 경우를 테스트하기엔 $N$이 너무 큽니다. 따라서 DP를 이용해서 $i$ 번째 쿠키까지 늘어나는 둘레의 길이 합의 구간집합 $S_i$를 구하도록 합시다.

$i = 0$ 일 때 쿠키를 자르지 않으므로 $0$ 입니다. 즉 구간집합으로 나타내면 $S_0 = {[0,0]}$ 입니다.

$i$ 번째 쿠키를 자르지 않으면 $0$, 자르면 $L_i$ ~ $R_i$가 늘어납니다. 따라서 $i$ 번째 쿠키를 자르지 않았을 때는 $0$을 더하므로 $S_{i-1}$그대로이고, 잘랐을 때는 $S_{i-1}$의 각 구간 $[l,r]$에 $[L_i, R_i]$ 를 더한 $[l+L_i, r+R_i]$ 의 집합 $S_{i-1}^\prime$ 이므로 $S_i = S_{i-1} \cup S_{i-1}^\prime$ 입니다.

즉 $S_1 = {[0,0], [L_1, R_1]}$, $S_2 = {[0,0], [L_1, R_1], [L_2, R_2], [L_1 + L_2, R_1 + R_2]}$… 입니다.

이런식으로 $S_N$을 구할 수 있고 이 때 시간복잡도는 $O(N \times |S|)$가 됩니다. 하지만 이런식으로 구하면 구간의 개수가 $i$가 1 늘어날때마다 2배가 되므로 $2^N$개가 될 수 있습니다. 따라서 구간집합을 합칠 때 겹치는 구간이 있으면 합쳐서 나타내도록 하고 $P$보다 큰 구간은 제외합니다. 이 때 각 구간의 너비는 최소 $min(R_i - L_i) = 2(\sqrt2 - 1)$ 이기 때문에 구간의 개수는 약 $P$ 개 이하로 있을 것입니다. 하지만 $P \le 10^8$ 이므로 여전히 많습니다.

하지만 한가지 사실을 더 캐치할 수 있습니다. $\sqrt 2 \times L_i \le R_i$ 이기 때문에 모든 구간 $[l,r]$ 에 대해 $\sqrt 2 \times l \le r$ 입니다. 가장 작은 구간부터 왼쪽에서 차곡차곡 쌓는다 생각하면, $2(\sqrt 2 - 1) \times \sqrt 2^{|S|} \le P$ 가 성립하고, 따라서 $|S| \le O(log P)$ 라는 것을 알 수 있습니다. 그러므로 구간집합을 잘 구하여 잘 합하면 $O(N\log P)$ 의 시간에 풀린다는 것을 알 수 있습니다.

Analysis에 의하면 $|S_K| ≤ 2K + 1$ 라고 하지만 증명을 해주지 않고 독자에게 맡겨놓았습니다.

Test set 1

  • $W_i = W_j$, for all $i$ and $j$.
  • $H_i = H_j$, for all $i$ and $j$.

모든 쿠키가 같은 모양이므로 $k$개의 쿠키를 잘랐을 때 늘어나는 둘레길이의 구간이 $[kL, kR]$ 입니다. 따라서 $P$ 가 각 구간에 들어있는지 $O(N)$에 구해도 되고, 또는 $P$보다 작은 가장 큰 $kL$을 $O(1)$에 구할 수도 있습니다.

Test set 2

위 풀이방법대로 $O(N\log P)$에 구할 수 있습니다.

후기

이번 R1은 sub-round 당 1500명이 R2로 진출하게 됩니다. 이 때문인지는 모르겠지만 이번 R1A는 예년보다는 쉬운 편이었던 것 같습니다. 물론 저는 Edgy Baking 문제에서 시간안에 나올거란 증명을 못하고 믿음을 가지고 제출했기 때문에 마냥 쉽다고만은 못하겠습니다.

이번 라운드에서는 우려했던 네트워크 문제는 없었던 것 같습니다. 그리고 문제페이지에서 Test set의 점수를 확인하는 기능과 자기가 제출한 소스보기 기능등이 추가되었습니다. 앞으로도 라운드 사이에 여러가지 기능들이 개발될 것으로 예상됩니다.

공유하기