8VC Venture Cup - Final Round

A

솔직히 5분도 너무 오래 걸린것 같다..

5분 pretest pass. AC

+ : 결국 어떤 문자열 S, T가 있을 때 S를 적당히 rotate해서 T로 만들 수 있느냐를 묻는 문제였다. 계속반에서 비슷한 문제 (기하 문제였다) 를 KMP로 푸는 사람들이 꽤 있었는데, KMP에 숙달되었거나 라이브러리가 있는게 아닌 한, 시간 버리고 점수 와장창 까이기 딱 좋은 방법이다.

적당한 기준 원소를 아무거나 잡고 (난 std::min_element 를 사용했다.) 그쪽을 기준으로 rotate하는 것이 가장 좋은 방법이라고 생각. stl 떡칠시 아주 빠르게 짤 수 있다. 특히 std::rotate가 꿀. 난 문제를 너무 대충 생각해서 코딩 + 시간이 살짝 말린 채로 시작했고 그 부분이 아쉽다고 생각한다. (다행이도 이후 결과에 전혀 영향이 없었다.)

C

B를 보고 너무 어려워서 C를 잡았는데, 세그먼트 트리를 아느냐 모르느냐 수준의 문제였다. 바로 짜서 냈다.

17분 pretest pass. AC

B

C를 잡고 다시 생각했는데 그렇게 어렵지 않았다. 사실 그래도 c보다 어렵지 않나 싶은데.

예외처리가 살짝 있는 문제다. systest fail이 두렵다..

24분 pretest pass. AC

+ : 2 * (a&b) + (a^b) = a + b 라는 identity가 있는거 같다. 이걸 아는 사람들은 꿀을 빤거 같은데.. 이런건 어디서 들은거지? (...)

D

http://usaco.org/index.php?page=viewproblem2&cpid=283 하나로 모든 것을 설명할 수 있다.

소스를 베낄까도 고민했지만 그냥 복기 수준으로 끝냈다. (베껴도 전혀 상관없었을거 같아서 후회중이다...)

38분 pretest pass. AC

E

D까지 너무 무난하게 올라가다 보니 E와 F가 남았는데, F가 겉보기에 참 쉬워 보였는데 사람들이 잘 못 풀기에, 난 당연히 못풀겠지라는 생각에 E를 잡았다.

일단 binary search 아이디어정도는 바로 생각을 했고. 그 후 한참동안 뭐지... 라고 고민을 하다가 트리 dp라는 것을 깨달았다. 내가 트리 dp를 영 못 짜서 자신이 별로 없었는데 아무튼 열심히 짜서 냈다. 열심히 짰고 참 오랫동안 짰다...

그렇게 O(nlgnlgai) 를 정말 열심히 짰고 끝나기 3분 전에 pretest를 pass했지만, systest에서 pass할지는 잘 모르겠다.

117분 pretest pass. AC

+ : binary search를 하면 "어떤 원소를 집을 수 있는지" 를 불리언 값으로 가지고 다닐 수가 있고, 이제 여기서 Tree DP를 돌리는 게 풀이이다. 편의상 루트를 고정시키면, 다음과 같은 Tree DP를 유도할 수 있다.

 * dp[i] = i번 노드에서 dfs를 시작했을 때, 가장 오래 갈 수 있는 preorder traversal

서브트리 안의 모든 원소가 집을 수 있는 원소일때 이를 "꽉 찬 서브트리"로 정의한다. dp[i] = 1 + (꽉 찬 서브트리의 dp[i] 합) + (안 꽉 찬 서브트리 중 dp[i]의 최댓값) 의 형태로 dp를 구할 수가 있으며, 이를 모든 루트에 대해서 시도하면 O(N^2)이다.

루트가 바뀌는 것이 문제인데, pdp[i]를 또 하나 정의한다. 임의의 rooted tree에 대해서 루트가 아닌 모든 정점에 대해서 정의되는 점화식이다.

 * pdp[i] = i번 노드를 루트로 했을 때, par(i)번 노드의 dp[i] 값.

pdp[i] 를 잘못 계산해 주면 성게에서 O(N^2)가 나오는데, 현명하게 잘 처리하면 해결할 수 있다. 식을 구했으니 답은 잘 처리하고 합쳐주면 나온다. 자세한 건 소스 코드를. http://codeforces.com/contest/634/submission/16416138

총평

초반도 너무 무난했고 솔직히 후반도 상당히 무난하게 흘러가서 "프리테스트만 다 맞았다면" top200 제외 Div1 2등이다. (계산기를 열심히 때려보니 top200 포함하면 27등인듯 하다.) 지난 성적과 비교해보면 월등히 좋다.

단지 systest를 여태 안하고 있어서 문제지...

제발 E를 맞았으면 좋겠다..

결과

E를 맞았고 2등으로 끝났다. top200 합산하면 종합 17등!

그래서 레드를 달았다.