Facebook Hacker Cup 2017 Round 3

결과

본선에 진출했다. 

그날 편두통이 있어서 걱정을 많이 했다. 편두통 심하면 아무 것도 못해서... 사실 대회 전에는 졸리고 편두통도 조금 있는거 같아서 거의 본선에 대해 체념 했는데, 다행히도 대회 중에 크게 컨디션 문제가 생기진 않았다. 편두통은 연휴 끝나면 병원 가서 끝을 봐야겠다. 타이레놀도 잘 안들어서 힘들다... 

딱히 모난 거 없이 했던 거 같다. A B C중에서 정말 못 풀겠다 싶었던 거는 없었고, 코딩도 그렇게 시간이 오래 걸리지는 않았다. 문제는 뭐 그냥 그냥 괜찮았던 거 같은데, 그래도 얼마 전에 버추얼 돌았던 2016 R3가 훨씬 재밌었다.

A. Salient Strings

Suffix array가 주어졌을 때 이를 만족하는 string을 복원하는 문제이다. 처음에 잘 모르겠어서 다른 문제로 넘어갈까 하다가, 그냥 그리디로 하면 되나 싶어서 그리디로 했고 다행히도 잘 됐다. 긴가 민가 했지만 실제로 suffix array를 만들고 비교해 보니까 assertion에 안 걸려서 그냥 신경 안 썼다. 

누가 본인이 2014년 즈음에 탑코더에 낸 문제라고 했다가, 또 한사람이 CERC 2008의 똑같은 문제를 들고 왔다. 해피엔딩 (....) 나는 저번 앳코더에 나온 POI 문제가 더 well-known이라고 생각한다.

B. Sluggish Security

N^2 dp approach는 빠르게 떠올릴 수 있지만 그 이상은 음.... 그래서 처음에 상당히 당황했는데 종이에 몇몇 케이스를 그려보니 결국은 ad-hoc 패턴 분석이라는 걸 깨달았다. 결국은 다른 큐에 있는 친구들을 매칭하면, 두 친구 매칭 쌍 사이의 사람들을 배치하는 경우의 수가 nCr * 2^K 정도로 나온다. 그냥 더러운 문제... 

예제가 약한 거 같아서 코드를 열심히 봤는데 졸려서 잘 안보이는 거 같기에 그냥 냈다. 저번 R2A도 그렇고 피드백 없는 대회에서 이런 문제를 꼭 내야 했을까? 라는 생각이 들었다. 그래도 예제가 강하다는 의견이 많아서 그 점은 다행인 것 같다 (채점 결과도 나쁘지 않고.)

C. Pie Packages

좀 신기한.. 형태의 weighted graph에서 모든 쌍 최단 경로의 합을 구하는 문제였다. B와는 다르게 첫 인상은 쉬워 보여서 크게 걱정은 안 했다. 예제도 강한 거 같아서 예제 나왔을 때 바로 냈다. 

몇가지 관찰을 하면 문제가 Sum(i < j) Min(D_i  + D_j, A_j - A_i, L - A_j + A_i) 를 구한다는 식으로 정리가 된다. (A_i는 1 -> i까지 원을 시계방향으로 움직였을 때의 거리, L은 원의 둘레, D_i는 중앙점에서의 최단 거리). A는 그냥 부분합이고 D는 다익스트라 한번에 구할 수 있다. 

여기까지 왔을 때 "이게 줄여져?" 하면서 당황했지만, A_j - A_i < L - A_j + A_i 를 만족하는 최대 j를 two pointers로 구하면 결국 특정 구간에 있는 j에 대해서 Min(D_i + D_j, A_j - A_i) 의 합을 구하는 문제로 바뀐다. 결국 등호 관계에 따라서 답이 D_i + D_j 내지는 A_j - A_i 중 하나로 결정되고, 이거는 binary indexed tree로 구할 수 있다. two pointer를 움직일 때 현재 보고 있는 구간의 원소들을 적당히 트리에 갱신해 주고, 또 등호 관계를 구간으로 변형해서 쿼리를 보면 된다.. 말보다는 식으로 쓰는게 나을 듯.

나는 이런 유형의 문제를 좋아하는데 다른 사람들이 어떻게 느꼈을 지는 잘 모르겠다. 나는 저 풀이가 모범 풀이가 아니라는 사실에 조금 놀랐는데, 모범 풀이는 이분 탐색을 조금 많이 (...) 하고 거기다가 부분합을 잘 끼얹는 식이었던 거 같다. 아마 내가 그렇게 짰으면 이 문제를 굉장히 싫어했을 것 같다 ㅋㅋ 더러운 게 컨셉이었으면 B로 됐지 왜 그랬나 싶다... 

D E는 조금 생각해보다가 별 생각이 안 나서 버렸다. 한 30분 넘게 남아서 그동안 놀았다. 

끝나기 전에는 이런 것도 했다 (...) 참고로 2 3 4 5등 모두 의미없는 서브밋이다. 트롤 4명 중 3명이 한국인이니 ugly korean이 아닐 수 없다 ㅎ;

소스 코드 : https://gist.github.com/koosaga/6ccd7ae51cbc3c2792a0f00885f71981