멘토교육 2주차 (IOI 2023 Day 2) 후기

  2주차 멘토교육으로는 6월 16일 13시부터 18시까지 IOI 2023 Day 2를 돌았다. 역시 성적은 좋지 않게 나왔지만 그래도 1주차보다는 향상된 것 같다. 하지만 Beech Tree 문제는 예전에 읽어본 적이 있고, 스코어보드를 보는 바람에 Overtaking 이 쉽다는 것을 알고 있는 상황이었음을 감안하면 여전히 금메달에서 상당히 떨어져 있다고 봐야 할 것이다.

  나보다 앞서서 어린 나이에 IOI 최상위권을 하는 학생들이 있다. 중국에서는 내가 IOI 여름학교 처음반에 입교한 나이인 14살에 코드포스 LGM을 찍은 사람도 있다고 한다. 다른 학생들에 비해 실력이 상대적으로 매우 뒤떨어져 있음을 인정해야 한다. IMO는 여섯 번 출전한 사람도 있고 최근에는 국내에서도 세 번 연속 금메달을 받은 사람이 있는데, 나는 우리나라 대표도 되지 못하였다. 자신의 상대적인 위치를 생각하다보면 멘탈이 나가는 일이 많지만 두 가지만 기억하기로 했다. 첫째로 나이에 비해 얼마나 하는지는 학문의 세계에서 중요하지 않다. IMO 주말교육 때 내가 비슷한 이야기를 하자 조교가 "수학 실력이 10년 뒤쳐졌으면 그냥 건강 관리를 잘해서 10년을 더 살면 된다"라고 짧게 말씀하신 적이 있다. 둘째로 이러한 열등감을 회피하려는 목적으로 핑계를 대는 것은 아무런 도움이 되지 않는다. 실력이 좋지 않다고 잘못한 것도 아니고 자책할 필요도 없지만, 이것과 스스로의 부족한 점을 냉정하게 바라보는 것은 전혀 다른 일이다. 이런 마음가짐으로 느리지만 꾸준히 공부하다보면, 분야가 매우 세분화되어 경쟁이 무의미해지는 박사과정 이후부터는 나의 분야에서 만족스러운 성취를 이루고 있을 것이라 믿는다.

 

  우선 모든 문제를 읽고 이해했다. 문제를 이해하는데만 총합 30분이 걸렸다. 문제가 6~8페이지로 한국 선발고사보다 훨씬 길기 때문이라는 핑계를 대고 싶지만 이는 마땅하지 않다. 문제 지문은 2페이지 정도였고, 함수 구현 세부 사항이나 Sample Grader 설명은 지문을 이해하고 나면 순식간에 읽혀야 하는 것이다. 문제를 이해한다는 것은 수식으로 표현된 것을 직관적인 현실 속의 상황으로 연관짓는 것이다. 나중에 수식적으로 기술된 많은 논문을 읽어야 할 것인데, 이런 IOI 문제조차 빠르게 이해하지 못해서는 안 된다. 물론, 아직 복잡한 상황을 이해하는 능력이 부족한 것이니, 오늘 했던 것처럼 문제 내용을 메모하면서 핵심을 파악하고자 노력하는 것은 바람직하고 앞으로도 많은 문제를 그렇게 하면 향상될 것이라고 믿는다.

  그리고 나서 beechtree 9점을 naive하게 풀어서 긁었다. overtaking은 있는 그대로만 구현해도 39점이 나왔다. robot은 그냥 비어 있는 직사각형에서 주변 상황을 보고 이동하는 문제인 6점을 풀었다. 이렇게 모든 문제 양수를 받은 것이 1시간 30분 정도였다. overtaking이 쉽다는 것은 앞서 언급했듯이 이미 IOI 2023 스코어보드를 보는 바람에 알고 있었다. 하지만 실전이었어도 보자마자 긁히는 점수의 양만 보고 바로 알 수 있었을 것 같다.

  이제 다시 beechtree로 돌아와, 그냥 모든 색이 같은지만 확인하면 되는 5점을 더 긁었다. 그리고 나서 수식으로만 기술되어 있는 문제 상황을 이해하려고 노력하던 중에, 각 노드에서 자식으로 뻗어나가는 간선들의 색 중 중복되는 것이 있으면 무조건 불가능하며, 간선들의 색의 집합은 임의의 두 개를 골라도 포함 관계여야 함을 알았다. 곧 이 조건과 문제가 필요충분조건이라고 판단해 버려서, bitset을 사용하여 $N\leq2000$ 섭태를 긁으려고 구현을 시작했다. 그러나 예제부터 반례가 나옴을 뒤늦게 알게 되었고, 필요조건에 불과한 위의 내용을 필요충분조건으로 만들기 위해 조건을 추가하는 것이 잘 되지 않았기 때문에 포기했다. 증명을 꼼꼼하게 살피지 않고 직관에만 의존하여 문제를 해결하는 좋지 못한 습관을 다시 한번 깨닫게 되었다. 색의 집합의 포함 관계는 중요한 관찰이지만, 이 관찰을 했다고 문제의 핵심적인 부분이 해결된 것은 아니고 다른 여러 아이디어가 필요한 것인데, 너무 섣불리 빨리 풀이를 마무리하고 싶다는 생각에 사로잡힌 것이다. 결국 점수가 14 39 6 정도인 상태에서 대회 시간이 절반밖에 남지 않았다.

  overtaking을 보려고 했지만, 이상하게도 이 문제에 집중이 잘 되지 않아서 robot으로 넘어왔다. 10점짜리 섭태2가 쉬워서 풀었고, 조금씩 변형하니 섭태3과 섭태4의 50% 부분 점수를 받아서 35점이 되었다. 섭태3과 섭태4를 해결하는 것이 가능하지도 않을까 잠시 생각해 봤고, 가능하다고 판단하여 구현도 시작했다. 하지만 구현하고 실행하는 가운데 오류를 파악하였고, 그 오류의 수정이 자명하지 않음을 알게 되어 포기했다. 역시 마찬가지로 생각한 알고리즘을 머릿속에서 검증해 보는 과정 없이 구현함으로써 시간을 허비한 것이다.

   2시간 조금 덜 남은 상황에서 overtaking의 나머지 섭태를 고민하기 시작했다. 관심 있는 버스 X보다 속력이 느린 버스만 고정시켜 놓고 생각하면 된다는 관찰을 했고, 이렇게 고정시켜 놓은 후에 X에 대해서만 계산하자 시간복잡도가 $O(MN+MQ\log N)$이 되어서 65점을 받을 수 있었다. 곧이어 구하는 과정에서, 추월 없이 이동('점프')을 한 다음에 나오는 위치는, 이미 고정되어 있는 $O(MN)$개 중 하나이므로, 이들에 대해 전처리를 해두면 된다는 생각을 하게 되었다. '점프'를 통해 얼마나 이동하는지를 빠르게 구해야 하는데, 처음에는 추월이 어떤 위치에서 일어났으면 그 다음에서도 일어난다는 말도 안 되는 생각을 했다. 이 생각의 근거는 X가 속력이 가장 빠르므로, 추월이 일어난 이후에는 X와 격차는 더더욱 벌어져서 X의 기대 시간보다 더 시간이 많이 걸린다는 것이었다. 그런데 추월이 일어나는 전제조건이 그 전 역에서는 X가 나중에 도착하는 것이니까 누가 봐도 말이 안 된다. 하지만 또다시 대충 생각하고 바로 구현해버리는 습관이 발현되어서 구현을 하였고 당연히 WA가 났다. 그리고 나서도 논리를 살필 생각을 안 하고 코드만 보다가 30분이 지나갔다. 결국 모르겠어서 혹시라도 논리가 틀린건 아닐까 하고, 이분 탐색을 하지 않는 것으로 코드를 바꿔보았더니 39점이 나왔다. 이를 보고 논리를 살피자, 이분 탐색 아이디어의 문제점이 보였고, 오히려 내가 생각한 것과 정반대로 추월은 단 한 번만 일어나기 때문에, 특정 위치에서 X보다 먼저 도착하는 버스의 수를 세는 방식으로 하면 된다는 것을 알았다. 버스의 수를 셀 때 lower_bound를 사용했기 때문에, 시간 복잡도가 $O((MN+Q)\log N\log M)$이 되었지만 3.5초니까 괜찮다고 생각하고 구현했다. 다행히 만점이 나왔고 실행 시간은 2.9초 근처였다.

  이러고 나니 대회 종료까지 15분밖에 남지 않았다. beechtree의 자잘한 섭태를 고민해 보았지만 실패로 끝났다.

  나의 문제점은 저번과 동일하다. 대충 관찰만 해놓고서는 풀었다고 착각하고 짜기 시작하고 틀리는 것을 반복하다가 시간이 다 가서 마땅히 받을 수 있는 점수를 받지 못한다. 앞으로 연습할 때 아이디어의 내용과 증명을 적어도 내가 코딩하면서 봤을 때 알아볼 수 있을 정도로는 적어두고 하는 습관을 가져야겠다.

  여담으로 overtaking 문제는 백준에서는 시간제한이 2초로 되어 있어서 TLE가 났다. lower_bound 함수가 불필요하게 사용된 부분이 있어서 해당 부분을 고치자 통과가 되었다.