VK Cup 2015 — Round 1 (online mirror)

이번 라운드는 할말이 별로 없는듯.. 푼 순서대로 서술한다

A
이 라운드가 dynamic scoring 인줄 몰랐다 맨 처음엔.
내가 너무 싫어하는 lexicographical + bracket 의 연속이라 정말 풀기 싫었는데
5분만에 E번을 푸는 사람이 나오면서 아 이거 dynamic scoring이구나를 깨닫고 던졌다.
결국 라운드 끝날 때 A가 가장 어려운 문제로 확인. 솔직히 딱 봐도 어려워 보인다.

E
5분만에 AC가 나와서 아 저거 복붙충 아니냐 **.. 은 농담이고. 쉬운가 싶어서 바로 봤다. (다만 3~5분 AC는 복붙이 맞는 거 같다)
처음 문제를 봤을때는 풀수 없음을 증명하는게 빠르지 않을까 (...) 하고 당황했는데
제약 조건을 본 후 그냥 평이하게 풀리는 문제임을 확인했다.
20분 pass. AC

B
디스크립션이 구려서 상당히 고생했다.
그냥 파라메터 하나 고정하고 잘 하면 되더라
40분 pass. AC

D
될법한 그리디를 짜서 냈다
70분 pass.
근데 안되나 보다.. WA

C
고생을 좀 했다.. 멘붕을 막 하다가 루트라도 짜보자는 심산으로 루트를 짰다. 무려 로그까지 붙은 O((Q+N)N^0.5lgN) 을 짰는데 커팅을 좀 하니까 2245ms / 3000ms 안에 통과가 되더라. 118분 pass (....)
다만 이번 라운드 pretest가 약하다 싶어서 실제로 통과가 될지는 의문이었고, 예상대로 통과 안돼서 TLE를 결국 띄웠다.

실제 풀이는 RMQ를 쓰면 꽤 쉽게 풀린다고 한다. 내가 멍청한 건지 원래 어려운 건지는 잘 모르겠다. 반반인거 같다 (...)

레드를 달겠다는 야심찬 생각으로 라운드를 시작했고 pretest가 약한 덕에 40등까지 올랐지만 현실은 25점 쬐끔 올랐다. (최종 120등) 그래 뭐 2개 맞아서 오른게 어디야... 다만 이번 라운드 자체가 전반적으로 짜게 반영이 된 거 같아서 다 맞았다 쳐도 레드는 못 갔을 거 같다.

4월 4일에 Zepto Code Rush가 있다고 하는데 이때는 레드 가고 싶다. 끗.