2023 국제정보올림피아드 대표학생 선발고사 후기

1차를 망해서 안 쓰려 했는데, 2차를 잘 봐서 쓰게 되었다. 지금은 대략적인 시간만 적고, 순위표가 나오면 자세한 내용을 적을 것이다. 글에 ?로 표기된 부분은 정확히 기억이 나지 않는 부분이다. 나중에 수정될 수도 있다.

 

풀이는 만약 업솔빙 한다면 다른 글에 업로드할 예정이다.

 

0. 결과

1차 선발고사

100 / 0 / 20 / 5 총점 125점, 전체 16등

2차 선발고사

100  / 0 / 100 / 60 총합 260점, 전체 4등

 

총합 385점, 전체 5등 (후보)

 

1. 1차 선발고사

https://www.acmicpc.net/category/800

국제정보올림피아드 대표학생 선발고사 2023

2월 9일 일요일 오후 1시부터 6시까지 5시간동안 진행되었다. 네 문제를 풀어야 했고 각 문제당 100점이었다.

 

0:00 ~ 0:49 (0 / 0 / 0 / 0)

10분정도 모든 문제를 읽었고, 1번은 보자마자 풀이를 찾았다. 바로 짰는데 예제가 나오지 않았다. 하나 덜 처리한 것과 구현에 실수한 부분이 있음을 알게 되었고, 고치는데 시간이 약간 걸렸다. 예제가 강해서 다행이지 예제가 별로 없었으면 이 문제에만 2시간을 썼을 수도 있었을 것 같다. 50분정도에 만점을 받았다.

 

0:49 ~ 1:00 (100 / 0 / 0 / 0)

제일 재밌어 보이는 4번 문제에 대해서 생각해보기로 했다. 5점 초과의 풀이가 10분동안 생각나지 않았고, 3으로 넘어갔다.

 

1:00 ~ 1:40 (100 / 0 / 0 / 0)

3번 문제가 다익스트라와 별로 다르지 않다는 사실을 찾았다. 풀테를 제외한 나머지 섭테도 그렇게까지 해결하는 것에 어려움이 없었다. 코딩은 풀테를 찾을 수 있으니 미뤄 두기로 하고, 만점 풀이를 생각했다. 만점 풀이도 떠올리는데에 그렇게 어렵지 않았는데, 센트로이드 트리와 Li Chao Tree를 사용하여 다익스트라에서 사용하는 각 연산들을 선형 미만 시간 복잡도로 최적화하는 것이 가능하다는 사실을 발견했다. 이 풀이를 연습장에 구체화했고, 어떻게 짤지 대략 생각해두었다. 그러나, 이 풀이가 대회가 끝날 때까지 코딩되는 일은 없었다.

 

1:40 ~ 2:10 (100 / 0 / 0 / 0)

만점 풀이를 바로 코딩하는 것은 약간의 도박이라고 생각해서(대회 당시에만 해도 Li Chao Tree를 구현할 줄 몰랐고, 워낙 연산이 복잡해 디버깅에 많은 시간을 허비할 가능성이 있었다), 제곱 풀이 다익스트라를 코딩해 보고 정상적으로 나온다면 만점 풀이를 짜는 것을 고려해보기로 했다. 그런데, 제곱 풀이를 짜서 2시간쯤에 제출해 보았는데 0점이 나왔다. 10분동안 디버깅해봤는데 오류를 못 찾았다. 그래서 다익스트라 풀이를 틀린 것으로 판단하고, 3번을 버렸다.

 

2:00 ~ 3:00 (100 / 0 / 0 / 0)

2번과 4번을 고민했다. 2번의 경우 10분정도 되는 생각 끝에 2번에서 11점 초과의 점수를 받는 사람은 3명 이하일 것이라는 판단을 한 뒤, 4번으로 넘어갔다. 그러나 시간을 50분 넘게 투자했음에도, 4번에서는 역시 5점 초과의 풀이를 전혀 찾지 못 했다.

 

3:00 ~ 3:10 (100 / 0 / 20 / 0)

화면을 넘기다가 우연히 코드에서 $10^{12}$ 스케일의 변수를 int자료형에 넣었음을 찾았다. 고치니까 바로 20점이 떴다. 결국 앞선 판단이 틀렸다는 것은 잘못된 판단이었고, 2시간도 안 남은 시점에서는 만점 풀이를 구현하기에는 위험 부담이 너무 컸다. 실제로 작년에도 1차 모의고사의 3번 문제인 히스토그램의 정해를 찾고, 2시간동안 구현과 디버깅을 반복하다 104점으로 끝난 경우가 있어서, 만점 풀이를 구현하지 말고 만점 풀이를 제외한 부분 점수를 긁기로 했다. 만점 서브태스크는 26점 정도라서, 가성비가 떨어진다고 판단한 것도 있다.

 

3:10 ~ 3:40 (100 / 0 / 20 / 0)

3번에서 긁어야 할 부분 문제는 2, 4, 5번 부분 문제로, 셋 다 풀이가 달랐다. 나는 뭔가 제일 간단해 보이는 5번 부분 문제부터 풀기로 했다. 내가 생각한 풀이는 O(2000N) 풀이로, 곱하면 2억이라 문제없이 동작할 것으로 예상했다. 구현하는데 약간 지체되어서 20분 정도 걸렸고, 제출했는데 TLE가 떴다.

 

3:40 ~ 3:50 (100 / 0 / 20 / 0)

앞의 코드를 최적화했다. 셋을 pq로 바꾸고, 프라그마에 inline 추가 등 별의 별 짓을 다 해봤으나 TLE는 고쳐지지 않았다. 그래서 이 서브태스크를 우선적으로 버리기로 하고, 2번 서브태스크로 넘어왔다. 그런데 내가 미리 생각해 둔 풀이가 틀렸음을 확인했다. 그래도 cht 풀이를 금방 생각할 수 있었다.

 

3:50 ~ 4:00 (100 / 0 / 20 / 0)

위의 풀이를 구현했다. 그런데 틀렸고, 알고보니 내가 잘못 생각했었다는 사실을 알게 되었다.

 

4:00 ~  (100 / 0 / 20 / 5)

이대로라면 그냥 망할 것 같아서, 마지막 희망인 4번 문제에 남은 시간을 쓰기로 했다. 그러나, 앞의 1시간과 지금의 1시간으로 총 2시간을 썼음에도, 5점 초과의 풀이는 결국 못 찾았다.

 

2. 2차 선발고사

국대가 안 될 것이라 가정하고 시험을 쳤다.

0:00 ~ 0:40 (0 / 0 / 0 / 0)

문제를 모두 읽었다. 2번과 3번의 지문을 이해하는데 약간 오래 걸려서 15분 넘게 걸렸던 것 같다. 느낌상 4번이 제일 쉬울 것 같아서 4번을 봤다. 각 남학생에 대해서 곱이 최대인 여학생 번호가 단조감소한다는 사실을 쉽게 관찰할 수 있었고, dnc opt와 같은 방식으로 풀 수 있다는 사실을 알았다. 총 25점 풀이를 생각했다. L2 = R2의 경우 분할정복으로도 시도하려 해 보았는데, 별 효과는 없었다. 일단 풀이를 찾게 될 수도 있으니 구현은 킵해두고 3으로 넘어왔다.

 

0:40 ~ 1:30 (0 / 0 / ? / 0)

쭉 3번만 생각했다. 예전에 비슷한 문제를 본 적이 있어서 풀 수도 있을 것이라 생각했고, 답이 1, 2일 필요충분조건을 찾았다. 이를 토대로 1, 2, -1중 하나가 답일 것이라는 추측을 하고, 코딩해 봤더니 틀리길래 아니라고 생각하고 접었다. 그 후 섭테 2부터 구현을 해서 맞았고, 이를 토대로 답은 "주어지는 구간을 최소한의 점을 선택해 각 구간 안에 최소한 하나의 점이 있도록 하게 되는 점의 최소갯수"라는 추측을 했고, 증명은 하지 못 했다. 검증해보기 위해 간단한 제곱 풀이를 생각해서 짰고, 맞았다.

 

1:30 ~ 2:10 (0 / 0 / 100 / 0)

3번 문제의 만점 풀이에 대해 생각해보았다. 예전에 보았던 IOI의 코끼리 문제에서 사용된 아이디어처럼 최대한 오른쪽으로 $i$개의 점을 배정하고, 왼쪽으로 $X-i-1$개의 점을 배정했을 때 $i$번째 점이 될 수 있는 값들을 알아낼 수 있다는 사실을 알아냈고, 이를 코딩했다. 약간 오래 걸렸는데, 구현이 햇갈려서 시간을 많이 끈 것 같다.

 

2:10 ~ 3:20 (100 / 0 / 100 / 0)

4번을 약간 더 하다가 1번으로 왔다. 예전에 비슷한 유형을 많이 본 적 있어서 1번은 보자마자 큰작 트리디피라는 사실을 바로 알았다. 구현이 약간 힘들었는데, 더블 카운팅의 아이디어로 각 정점과 그 부모를 잇는 간선이 몇 번 사용되는지를 찾아야 하고, 이를 셋으로 관리할 수 있다. 이것저것 함수를 만들어서 실수하지 않도록 짰음에도 불구하고 셋에서 처리를 하나 잘못해서 시간을 약간 날렸다.

 

3:20 ~ 4:00 (100 / 0 / 100 / 0)

4번에 대해 좀 더 고민했다. 섭테 3의 풀이를 발전시키려 했는데, 잘 되지 않았다. 그러다가 문득 루트로그 풀이를 생각해 보게 되었다. N명의 남학생을 1000명씩 묶어서 각각 dnc opt를 하는 방식이다. 처음 생각했을때는 NMQ 전부 10만에 tl 6초라서 당연히 안 될 것이라고 생각하고 넘겼는데, 나중에 보니 dnc opt의 소스 코드가 굉장히 가볍고 빨라 보인다는 것을 알게 되었다. 그래서 이 코드를 짜기로 결정했다.

 

4:00 ~ 4:35 (100 / 0 / 100 / 60)

루트로그 풀이를 짰다. 약간의 구현 실수가 있어서 한 번 틀렸고, 그 다음 제출에서 맞았다. 루트로그라서 속도를 기대하지 않았는데, 모든 데이터에서 800ms정도에 돌았다. 생각보다 엄청 빨랐다. 

 

4:35 ~ 5:00 (100 / 0 / 100 / 60)

딱히 더 이상 풀 문제가 안 보였다. 문제 2번도 시도해보았으나, 섭테 1에서 TLE가 떴다.

 

3. 후기

2차 선발은 전체적으로 구현에서 약간 말린 점을 제외하면 잘 본 것 같은데 1차 선발고사에서 200을 넘지 못한 것이 너무 아쉽다. 3번을 풀이를 찾았을 시점부터 짜기 시작했다면 늦어도 3시간 안에는 AC를 받았을 수 있었을 것 같은데, 판단을 잘못 한 것 같다.

 

지금 와서 생각해 보니 구현 문제로 문제를 푼 시간이 조금씩 지체된 것 같다. 너무 늦은 것 같지만, 구현 연습과 업솔빙을 잘 해야겠다는 생각이 든다.