알고리즘/국대 멘토교육

대회실습 7 (6.10)

kdh9949 2017. 6. 10. 01:26

<IOI 2016 Day 1>


molecules, railroad, shortcut 문제를 풀었다. 사실 세 문제 다 예전에 본 적이 있는 문제였긴 하다.

가장 먼저 molecules를 풀었다. 탐지 범위가 분자들간의 무게 차이의 최댓값 이상이라는 조건 때문에 주어진 수들을 정렬한 뒤 임의의 [s, e] 구간의 합만 고려해도 충분하다는 사실을 알 수 있다. 각 구간의 길이에 대해 이분탐색으로 간단히 조건을 만족하는 구간이 있는지 판별할 수 있다.

그 다음에는 railroad와 shortcut을 각각 봤는데, 둘 다 일단은 아무 생각이 들지 않았다. railroad는 34점 풀이까지는 간단히 생각할 수 있었어서 일단 보류한 뒤 shortcut에 대해 고민을 좀 한 결과, 케이스를 적절히 나누고 전처리를 몇 가지 하여 모든 지름길을 놓는 경우에 대해 새로운 그래프의 지름을 O(N)에 계산하는 O(N^3) 풀이를 짜서 38점을 받을 수 있었다. 그 뒤 railroad 34점을 빠르게 받고 점수를 더 받을 수 있는 곳을 찾아 보았다.

railroad 64점이 뭔가 그리디가 되게 생겨서 (사실 현수가 작년에 그리디로 점수를 받았다는 이야기도 들은 적이 있다...) 뭔가 각 롤러코스터에 대해 끝점에서 나와서 가장 가깝게 있는 (자신이 아닌) 시작점으로 이어주면 될 것 같다는 생각이 들어 짜서 냈더니 맞았다.... 그래서 풀이가 맞는 줄 알고 거기서 생각을 더 해 나갔는데 아무 것도 더 안 되었다. (사실 그건 애초에 틀린 풀이였다)

나머지 시간 동안 shortcut도 고민을 해 보았는데, 지름길이 추가된 두 정점 사이의 점에 걸린 거리의 식에 min과 max가 복잡하게 섞여 있어서 도저히 더 줄일 구석이 보이지 않았다. 결국 더 이상의 점수를 받지 못하고 대회가 끝났다.


2번이든 3번이든 대회 중에 푼 사람이 정말 신기하다. 올해도 이런 문제 셋이 나온다면 정말 힘들 것 같다. 공부를 더욱 열심히 하는 수 밖에 없겠다.

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

대회실습 7 (6.11) + 멘토교육 마무리  (3) 2017.06.11
대회실습 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