대회실습 4 (5.28)

<CEOI 2016>

Day 2 set에서 내가 예전에 풀었던 적이 있는 router를 빼고 kangaroo가 들어갔다.

kangaroo를 보고, 문제가 뭔가 쉬울 것 같아서 먼저 잡았다. 너무 급하게 달려들었는지 생각이 잘 정리가 되지 않았고, 51점 풀이 같은 것을 생각한 뒤 일단 넘어갔다.

match는 처음 봤을 때는 아무런 생각이 들지 않았다. 뭔가 Greedy한 가정을 하나 세워야 할 것 같은데 그것이 뭔지 잘 보이지 않아서 일단 또 넘어갔다.

popeala는 문제를 읽자마자 "dp 최적화 문제"라는 생각이 바로 들었고, O(NT^2) Naive dp를 세워 일단 코딩을 했다. 그 다음에 좀 더 생각을 해 본 결과, i번 나눈 dp값에서 (i+1)번 나눈 dp값을 구할 때 더해지는 cost값을 N개의 구간으로 나누면 각각의 구간에 대해 RMQ를 때려 값을 빠르게 구할 수 있다는 생각을 했다. 그런데 그렇게 하면 시간이 O(NSTlogT)가 걸리는데 N, S가 50이고 T가 2만일 때 계산해 보면 8억 정도가 나와서 약간 절망에 빠졌다.

이렇게 있다간 아무 것도 안 될 것 같아서 kangaroo로 넘어가 생각을 다시 정리한 뒤 51점을 긁었다.

다시 popeala로 넘어와서 log를 뗄 방법을 한참 생각하다가 생각이 안 나서 그냥 26점이나 긁자 하는 마음으로 log 붙은 코드를 냈는데 시간 안에 나왔다(??!) segment tree를 사용하면 쿼리로 물어보는 구간들이 작을 때가 많아 그것 때문에 시간이 좀 줄겠다는 생각은 했지만 시간 안에 나올 줄은 몰랐다.

아무튼 match로 넘어와서 생각을 약간 해 본 결과 "각 문자 별로 가능한 한 가장 뒤에 있는 자기와 같은 문자와 매칭시키는게 무조건 이득이다"라는 사실을 알 수 있었고, 증명을 대충 해 본 뒤 N^2으로 코딩을 해 봤더니 47점을 맞길래 다행스러웠다.

1시간 좀 넘게 남았길래 "나머지 둘 중 하나는 시간을 쓰면 풀 수도 있겠다"라는 생각이 들어 번갈아가면서 열심히 고민해봤지만, 결국 끝날 때 까지 더 이상의 소득은 없었다. 이 마지막 1시간이 가장 아쉬웠다.

초반에 좀 말릴 뻔 했는데 그래도 망치지는 않은 것 같아 다행이다. kangaroo나 match나 둘 다 "복잡하다"기 보다는 진짜 "창의적" 생각을 해 내야 풀릴 것 같은 문제인데 이런 걸 생각하는 것은 어떻게 연습해야 할지 잘 모르겠다. 그리고 저번에 못 풀었던 code breaking 문제를 아직도 못 풀었는데 (솔직히 지난주에 조금만 덜 놀았으면 풀었다) 이번 주는 연휴도 있고 하니 제발 그만 놀고 열심히 해서 학교 과제든 멘토교육 문제든 다 끝내야겠다.