알고리즘/국대 멘토교육

대회실습 7 (6.11) + 멘토교육 마무리

kdh9949 2017. 6. 11. 01:01

<IOI 2016 Day 2>

paint, messy, ailen 문제를 풀었다. 일단 messy가 interactive고 뭔가 별로 안 어려워 보여서 먼저 시작했다.

제한을 보면 N=128인데 입력, 조사 쿼리가 각각 896=7*128=NlogN이라 딱 봐도 뭔가 반씩 나눠서 잘 하면 되겠다는 생각이 들었고, 일단 처음에 "1000...00", "01000...00" 같이 1개만 1인 문자열을 처음 반 개만 만들어서 넣어 보면 처음 반이 어디로 mapping되는지 알 수 있다는 것에서 시작하여, 그 다음에 분할을 어떻게 할 지 생각하다가 일단 보고자 하는 구간 [s, e]의 모든 수가 어디로 가는지 안다면 나머지 부분에 다 1을 채워 넣으면 된다는 것을 생각하고, 이를 이용해 간단한 분할 정복 풀이를 짜서 맞았다. 풀이가 빠르게 생각난 게 다행인 것 같다.

다음으로는 paint를 봤는데, 각 자리에 X, _가 들어갈 수 있는지를 dp를 통해 전처리를 해 놓고 빠르게 본다는 생각으로 접근했고, 처음에는 100점 풀이를 생각한 줄 알았는데 알고 보니 조건이 더 세세한 게 많아서 덕지덕지 붙이다 보니 결국 O(N^3)이 되어 버려 80점이 되었다. 그 다음에 다시 그걸 줄이려고 보니 좀 힘들 것 같아 ailens로 넘어갔다.

ailens 문제는 dp식을 써 보면 O(N^2K) dp식을 쓴 뒤 정리를 하면 바로 전형적인 Convex hull trick 꼴이 나온다. 이것만 해도 60점이 나온다. 식을 쓸 때 조건 하나를 빼먹고 써서 잠깐 헤메다가 그걸 고치니 바로 60점을 받을 수 있었다.

나머지 시간동안 ailens와 paint 문제에 대해 각각 시간을 더 쏟아 봤지만 소득이 없었다. (사실 졸려서 별로 열심히 생각을 안 했다...)


대회 후 IOI 2016 점수판을 보니 금 딴 사람들은 paint를 다 풀었다. (사실 은 딴 사람들도 대부분 풀었다) 가끔가다 이렇게 남들이 다 푸는 문제를 혼자 못 푸는 경우가 생기는데, (작년, 올해 APIO 때도 그랬고 계속반 때 IOI 2011 crocodiles인가? 풀 때도 그랬다.) 침착하게 생각을 하지 못 하고 계속 이상한 데 가서 고민하는 경우인 것 같다.


----------------------------------------


대회 실습을 총 7번 했으니까 21문제를 푼 셈인데, 처음에는 그래도 대회 중에 2개씩 풀다가 갈수록 1개밖에 못 풀게 된 것 같다. 대회 중에 못 푼 (다시 말해 일정 수준 이상으로 어려운) 문제를 온전히 혼자 생각해서 푼 게 kunai가 마지막이었다는 것이 가장 아쉬운 점이다. 멘토 교육 중에는 학교를 같이 다니고 있으니 학교에서 나오는 숙제나 수행 평가 등과 병행을 해야 했는데, 맨날 시간이 좀 많을 때는 아무 것도 안 하고 놀다가 결국 시간이 임박하면 학교 수행평가를 먼저 하고 교육 문제는 충분히 생각할 시간을 갖지 않았던 것 같다.

교육 담당 조교님의 코멘트를 정리하면,

- 장점 : 코딩 습관이 좋다(가독성이나 논리의 명확성 면에서), 기본기가 충분하다(긁을 걸 못 긁은 경우가 거의 없다)

- 개선점 : 어려운 문제를 생각하는 능력을 기를 필요.

이 정도가 된다. 곧 시작될 합숙 교육에서 그런 어려운 문제를 풀어 내는 능력을 최대한 길러 내야 IOI에 갔을 때 후회 없는 성과를 낼 것 같다.

'알고리즘 > 국대 멘토교육' 카테고리의 다른 글

대회실습 7 (6.11) + 멘토교육 마무리  (3) 2017.06.11
대회실습 7 (6.10)  (0) 2017.06.10
대회실습 5 (6.4)  (0) 2017.06.04
대회실습 4 (5.28)  (1) 2017.05.28
대회실습 3 (5.21)  (0) 2017.05.21
대회실습 2 (5.12)  (2) 2017.05.13