Facebook Hacker Cup 2017 Qualification Round & Round1

1월 1주, 2주에 페이스북에서 주최하는 해커컵 Qualification Round와 Round1 이 지나갔습니다.

주말에 귀찮음을 간신히 부여잡고, 각각 가장 쉬운 한문제씩 풀어봤습니다. 

1. Progress Pie

보시면 아시겠지만, 이 문제는 입력으로 점이 주어졌을때, 특정 영역에 속하느냐를 묻는 문제입니다.

그런데 하필 원이라, 수학지식을 동원해야 할것같습니다.

두 가지를 만족하면 되겠죠.

- 주어진 점과 중심의 거리가 반지름보다 작아야한다.

- 중심점과 주어진점 사이의 각도가, 주어진 각도보다 작아야한다. (주어진 각도라 함은 진행률을 각도로 환산한 값을 의미)

두 점 사이의 각도? 검색하면 잘 나옵니다. (예를들면, http://yangpro.github.io/play-with-canvas-trigonometry/)

약간 고쳐줘야 하는게, 문제에서는 수직일때가 0도이므로, 수학함수를 이용한 결과를 그에 맞게 범위조정을 해줘야합니다.

코드: https://github.com/xgate/competition/blob/master/hackercup/2017/PogressPieQR.cpp

2. Pie Progress

이 문제에서 현실과 다른 포인트가 있습니다.

그건 미래에서 과거를 선택할 수 있다는 것이죠.

1일차에 팔던 파이를, 그 가격 그대로, 비용 최적화를 위해 5일 뒤에도 구입할 수 있다는 점입니다.

그런데 한가지 제약이 있는게, 하루가 지날때마다 적어도 하나의 파이는 있어야 합니다. (안그러면 굶어죽으니까요)

또하나 알수있는건, 특정일에 연속으로 파이를 살때는 무조건 싼것부터 사는게 좋다는 것입니다. (= 정렬을 해라)

이 조건들을 고려해서 저는 비용의 증가분을 우선순위 큐에 넣고, 하루에 한 번씩 가장 적은 비용을 고르도록 구현했습니다.

코드: https://github.com/xgate/competition/blob/master/hackercup/2017/PieProgressR1.cpp

Round1에서는 한 문제만 더 풀었으면 Round2로 올라갔을텐데 주말의 힘이란 참 무섭습니다. ^^

(하긴 풀었다고 해도 맞췄다는 보장이...)

솔루션들

- QR, R1

4월에 열리는 구글 코드잼에 도전을 할지 모르겠군요. 

해커컵은 조용히 내년을 기약합니다.