본문 바로가기

Computer Science/Competition

Google Hash Code 2020 참가 후기

생애 처음으로 Google Hash Code에 참가했습니다.

저는 import_torch_as_tf 라는 이름의 팀으로 김민철, 김상범 님과 함께 참가했습니다.

최종 26,282,007점이라는 점수로 세계 1,119등, 한국 24등 이라는 다소 저조한 성적을 냈지만, 그래도 나름대로 재밌었습니다.

 

각 문제에 대해 저희 팀의 풀이를 소개하자면, 다음과 같습니다.

스포일러가 될 수 있으니 주의해주세요!

 

B - read on / 5,822,900

데이터를 살펴보면 sign up time 순으로 출력하면 해결할 수 있음을 알 수 있습니다.

C - incunabula / 5,521,060

Library를 sign up time이 작은 순으로 정렬하고, library 안의 책들을 그리디하게 정렬하면 충분한 보상을 받을 수 있습니다. 저는 그 후 그리디한 랜덤 스왑을 몇 번 더 해서 점수를 소폭 올렸습니다.

D - tough choices / 5,028,530

To be updated

E - so many books / 4,593,191

데이터의 특성을 파악하지 못해 결국 휴리스틱을 이용해 그리디하게 골라주었습니다. 휴리스틱에 사용되는 상수의 경우 최적화 하여 local maximum solution에 다가가기는 했습니다.

F - libraries of the world / 5,316,305

Library 및 book의 정렬 순서를 하나의 상태로 보고, 상태 간의 전이 연산으로

- 두 library의 순서를 바꾸거나

- 한 library내의 두 책의 순서를 바꾸는

것을 생각해봅시다. 두 상태 간의 거리를 이동하기 위한 최소의 연산 횟수로 정의합시다.

저희 팀은 그리디 알고리즘을 통해 적당히 좋은 상태에서 시작해 거리가 특정 값 이내인 랜덤한 상태를 탐색하고, 더 좋은 상태이면 이동하고, 아니면 머무르는 간단한 방법을 통해 약 531만점을 받았습니다.

'Computer Science > Competition' 카테고리의 다른 글

UCPC 2020 참가 후기  (0) 2020.08.01
2019 ICPC 한국 리저널 인터넷예선 풀이  (0) 2020.06.03
Google Code Jam Round 1C  (0) 2020.05.03
Educational Codeforces Round 86  (0) 2020.04.30
Google Hash Code 2020 참가 후기  (0) 2020.02.21