2020 Google Code Jam Round 2 후기

결과

A. Incremental House of Pancakes

  대소 관계가 한 번 바뀐 후에는 양쪽에서 번갈아가며 가져가면 된다는 사실을 관찰하고 나면, 대소 관계가 언제 처음 바뀌는지, 언제 끝나는지를 각각 이분탐색해서 문제를 해결할 수 있다. 급하게 짜느라 식이 꼬여서 자꾸 Off by one 에러가 생겼다. 결국 45분이 되어서야 첫 제출을 했고, 틀렸다. 두 번의 제출을 더 한 끝에 56분쯤에 AC를 받을 수 있었다. A에서 1시간이나 사용했기 때문에 여기서 멘탈이 좀 나갔다. 이런 유형의 문제에서 자꾸 말리는 경향이 있는데, 빨리 풀지는 못해도 AC는 한 번에 받을 수 있게 노력해야겠다.

 

B. Security Update

  Hidden까지 풀려면 케이스 노가다를 많이 해야 할 것 같아서 Visible만 간단한 그리디로 긁고 넘어가기로 했다. 숫자가 작은 정점부터 보면서 간선 가중치를 적절히 배정해주면 된다. 이상한 실수를 해서 이거마저도 2트를 했다. ㅠㅠ Hidden 풀이가 바로 보이지 않았기 때문에 결국은 좋은 선택이었던 것 같다. 실제로 C에서도 말려서 거의 끝날 때쯤 맞았기 때문에 B번 Hidden까지 풀고 넘어가려고 했으면 결국 1000등 안을 못했을 것 같다. 그와 별개로 Hidden 풀이는 케이스 노가다 없이 깔끔하게 풀린다. 그냥 Visible 푼 것과 비슷하게 두 리스트를 그래프에서 적절히 합쳐주면 된다.

 

C. Wormhole in One

  먼저 N개의 점으로부터 $O(N^2)$개의 각도 후보를 뽑아낼 수 있고, $O(N^2)$개의 각도 후보에 대해서 문제를 따로 해결한 뒤 최댓값을 취해 주면 된다는 생각을 할 수 있다. 어떤 각도에 대해서 어떤 점 a에서 점 b로 갈 수 있을 때, a와 b를 연결해 보자. 그러면 N개의 점은 몇 개의 체인을 이루게 되는데, 여기서 중요한 정보는 각 체인에 속한 점의 개수뿐임을 알 수 있다.

 

  여기서부터는 엄밀하지는 않지만, 나는 다음과 같이 접근했다. 체인에 속한 점의 개수를 $C_1, C_2, ... , C_k$로 나타내 보자. $C_i$가 짝수이면 체인에서 적절히 인접한 점끼리 웜홀을 이어 줘서 i번째 체인에 속한 모든 점을 사용하게 하도록 만들 수 있다. 반면 $C_i$가 홀수이면 조금 애매해진다. 예제에 이런 예시가 있었는데, 1-2-3 체인과 4-5-6 체인이 있을 때 1과 3을 웜홀로 연결하고, 4와 6을 웜홀로 연결하고, 2와 5를 웜홀로 연결하면 모든 점을 지날 수 있게 된다. 여기서 약간 이상한 생각을 할 수 있는데, 1보다 큰 홀수 $C_i, C_j$가 있을 때 i번째 체인의 가운데에 속한 점 x와 j번째 체인의 가운데에 속한 점 y를 웜홀로 이어 주고, j번째 체인의 처음과 끝을 웜홀로 이어 주면, 두 체인이 마치 크기가 $C_i + C_j$인 체인처럼 행동한다는 것을 알 수 있다. 그리고 결국 길이가 홀수인 체인 두 개를 길이가 짝수인 체인 하나로 만들어줄 수 있다는 결론이 나온다. 그래서 길이가 1보다 큰 홀수인 체인들을 짝수 체인들로 만들어준 후 공의 경로의 시작과 끝에 min(남은 체인의 수, 2)개만큼의 점을 더 지나도록 해 주면 AC를 받을 수 있다. 

 

  각도정렬하기 귀찮아서 $O(N^4)$을 짜려다가 시간 초과가 날 것 같아서 각도정렬을 사용하는 $O(N^3 log N)$ 풀이를 짰다. 그런데 오퍼레이터 정의 실수를 해서 필요 없는 시간을 꽤 허비했고, 끝나기 10분 전에 겨우 제출했다. 다행히도 Hidden까지 맞았고, 428등으로 대회가 끝났다.

 

D. Emacs++

 D번 문제는 읽지도 못했는데 Visible이 예전에 UCPC에 출제됐던 문제와 거의 같다고 하니 풀어봐야겠다. 

 

---

Summary

  B Hidden을 거른 판단 덕분에 1000등 안에 들 수 있었던 것 같다. 작년에 이어서 티셔츠를 또 받아서 기쁘다 ㅎㅎ 

Round 3이 중간고사 일주일 전인데 제대로 칠 수 있을지는 잘 모르겠다... ㅠㅠ