Google Code Jam: Round 2 2020

드디어 Round 2다.

세번의 기회가 주어졌던 Round 1과는 달리 이제는 단판승부이기 때문에 정말 정신 차리고 필요한 모든 연료(?)까지 옆에 비축해두고 대회를 시작했다.

---

1. Incremental House of Pancakes

There are two stacks of pancakes. The height of each stack is given as input.

You are to serve customers. The $i$th customer requires $i$ pancakes to be served.

$i$ pancakes will be given from the stack of higher height. If the two stacks are of equal height, the left stack will be chosen.

When there aren't enough pancakes on the stack, you stop serving customers.

초기 스택의 높이가 주어졌을 때, 총 몇명의 customer를 serve할 수 있으며, 각 stack에 남은 pancake의 수는?

 

첫번째 서브태스크는 그냥 위의 논리를 직접 구현하면 통과 가능한 조건이었다. 문제를 더 빠르게 풀 좋은 방법이 빠르게 떠오르지 않아서, 일단 점수를 받아두자는 생각에 11분만에 구현하여 제출했다. 이왕 짜는거, 더 빠르게 작동하는 C++로 구현하였다. 그러고는 다음 문제로 넘어가서 고민을 좀 했다.

 

하지만 두번째 문제는 더욱 어려워보였다.

그래서 다시 첫 문제로 돌아와 첫 문제의 두번째 서브태스크에서 주어진 범위 내의 최대 값을 입력시켜 내 C++ 코드가 동작하는 시간을 측정해 보았다. 측정할 것도 없이 너무 느렸다.

 

결국 두 스택의 높이가 같은 경우, 각 스택에서 번갈아 serving을 하게 된다는 점에 주목하여 풀이를 구상하기 시작했다. 번갈아 serving을 하는 경우, 최종으로 serving하는 pancake 수가 주어진다면, 각 스택에서 빼야 하는 pancake의 수는 등차수열의 합으로 $O(1)$ 시간에 구할 수 있다. 고로 최종적으로 serving 할 수 있는 최대 pancake의 수는 이진탐색으로 빠르게 찾을 수 있다.

 

문제는 두 스택의 높이가 다른 경우였다. 두 스택의 높이가 다른 경우, 이를 최대한 같게 만듦으로써 이미 해결한 두 스택의 높이가 같은 경우의 논리를 적용시키고자 하는 시도가 자연스러웠다. 이진탐색을 이미 떠올린 시점에서, 두 스택의 높이가 비슷해질 때까지 더 높은 스택에서 빼야 하는 pancake의 수를 계산하는 것은 간단하였다. 남은 문제점은, 더 높은 스택에서 pancake들을 serving해서 두 스택의 높이가 비슷해진다 한들 두 스택의 높이가 같아지지는 않는다는 점이었다. 하지만 잠깐 생각해보면, 두 스택의 높이가 같아지지 않아도, 더 높은 스택이 낮은 스택의 높이보다 작아지는 순간, 두 스택에서 serving을 번갈아 하게 된다는 사실을 깨달을 수 있다.

문제 해결이다.

 

스택의 높이가 같은 경우 왼쪽 스택에서 serving을 한다는 규칙 때문에 예외 처리를 생각하느라 구현이 늦어졌다. 결국 한시간을 1분 넘겨서 제출하였다. 코드포스 Div. 2 기준 B 혹은 C 수준의 문제인 것 같은데, 너무 시간을 많이 쏟았다.

---

2. Security Update

컴퓨터 네트워크가 그래프로 주어진다. 첫번째 컴퓨터로부터 업데이트가 네트워크를 따라 퍼져나간다.

각 컴퓨터에 대해, [1. 그 컴퓨터보다 먼저 업데이트가 적용된 컴퓨터의 수, 2. 그 컴퓨터가 업데이트된 시간] 중 하나의 정보만 주어진다.

네트워크의 각 간선 가중치(통신에 소요되는 시간)을 맞혀야 한다. 단, 모든 가중치는 1 이상의 정수이다.

 

문제 설명을 읽어보니 어려울 것이라는 예감이 든다. 푼 사람의 수를 보고, 첫번째 서브태스크만 해결해 보기로 결정했다. (이 시점에서 이미 1000등 안에 드는 것은 어렵다는 것을 인지했었다.)

 

첫번째 서브태스크는 1번 종류의 정보만 주어지는 경우이다. 각 컴퓨터보다 먼저 업데이트된 컴퓨터의 수를 그냥 그대로 그 컴퓨터가 업데이트된 시간이라고 가정하고, 간선간의 가중치는 각 컴퓨터가 업데이트 된 시간의 차이의 절댓값으로 설정하였다. 만약 간선에 연결된 두 컴퓨터가 동시에 업데이트됐다면, 그 간선의 가중치는 어떤 값으로 설정해도 문제가 없다. 코드에서는 1로 설정해두었다.

이 간단한 풀이를 떠올리는 데에도 거의 한시간이 걸렸다. 여러 unsuccessful 시도들 끝에, 이 방법으로 첫 서브태스크를 통과시킨 것이 1시간 59분이다.

 

남은 대회시간 30분은 스코어보드를 구경하며 보냈다.

---

총평

현재 1795등이다. UPD) 1791등으로 확정되었다.

작년의 2339등보다는 소폭 상승했지만, 아직 나는 많이 부족한가보다.

언젠가는 Round 3를 가겠지... 그 언젠가가 너무 먼 미래는 아니었으면 좋겠다.

 

연습지