2025 KAIST RUN Spring Contest 후기

대회가 끝난것은 사실 꽤 이전의 일이긴 하지만, 어쨌든 운영진중 누군가는 후기를 작성할 필요가 있을 것 같아서 기억에 의존하여 후기를 적어본다. 사실 굉장히 우여곡절이 많았던 대회였다고 생각한다...

 

1. 아이디어 선별 과정

선제는 기본적으로 나와 RUN의 현 회장인 flappybird가 진행하였다. 사실, 1월쯤부터 문제를 뽑아냈었던 것 같은데, 이미 이 시점부터 굳이 call for task를 받지 않고도 (살짝 퀄리티가 떨어지긴 하겠지만) 봄대회랑 가을대회까지 전부 열 수 있는 양의 문제가 준비되어 있었어서, 콜포태를 받을지 말지에 대해 살짝 고민하긴 했었다.

 

근데 역시 콜포태를 열어두면 종종 꽤 좋은 문제가 들어온다는걸 알고 있었고, 무엇보다도 본인이 5~6문제 이상을 세팅하는건 극심한 고통을 겪게 될 것 같았기 때문에 그냥 콜포태를 열기로 하였고, 이러한 선택의 정당성을 잘 증명하듯이 좋은 문제들이 많이 들어왔다. 사실, 선제에 대해 더 말하기에는 아이디어에 대한 비밀 엄수를 해야 하는 관계로 이 과정에 대해서는 많이 얘기할 수 없었다.

 

2. 세팅과정

사실, 본 대회는 내가 다른 출제에 참여했던 대회들에 비해 상당히 세팅준비가 늦게 시작하긴 했다...일단 본인이 이번에 6개의 전공과 2개의 동아리 임원을 맡으면서 PS수련과 출제까지 해야했던 관계로 조금 시간이 없었던 것도 있었고, 대회를 아주 주도적으로 운영한 적이 있는 인물도 없었기 때문에 이런 차질이 생겼던 것 같다.

 

사실 타 문제들같은 경우에는 인터랙티브같이 세팅이 까다로운 문제는 없었고, 많은 출제자 분들이 기본적으로 숙련된 출제경험이 있었던 만큼 큰 문제는 없었지만, 본인이 이번에 출제한 문제의 경우에는 알다시피 인터랙티브와 인터랙티브 투스텝 기하가 있었기 때문에, 세팅하는데에 심각한 애로사항을 겪었다.

 

비록 모든 문제의 세팅현황을 완전히 꿰뚫고 있었던 것은 아니지만, 각 문제들의 세팅과정에 대해 간략히 설명해보면, 다음과 같다.

 

A. Bubbler님이 워낙 출제경험이 많으시고, 쉬운 문제 포지션의 배치 문제였기 때문에 크게 걱정하지 않았고 실제로도 별 이슈가 없었다.

 

B. 이것도 사실 쉬운 문제 포지션의 간단한 배치 문제였기 때문에 큰 이슈는 없었다.

 

C. 원래는 다른 문제가 이 포지션을 차지할 예정이었는데, 해당 문제의 정해가 터져서 4월즈음에 flappybird가 다른 문제를 적당히 만들어서 교체했다. 사실 여기까지 쉬운 문제 포지션이었어서 큰 이슈가 없었다.

 

D. 사실 원래는 Sheriruth가 F였고, 운영진들 사이에서는 D~F까지는 난이도가 개인차에 따라 적당히 갈릴거라고 예상했었다. D가 증명보다 pba가 상대적으로 쉬운 감이 있어서 생각보다 D의 포지션에 알맞았던듯하다. 문제 자체에 대해 말해보면, 굉장히 필요충분조건이 깔끔하고 construction도 재미있게 할 수 있어서 좋은 문제였다고 생각한다. 역시 Bubbler님이 세팅했고, 애초에 데이터를 넣는다고 할만한게 없어서 세팅 자체는 무난하게 진행되었던 것 같다.

 

E. 원래 해당 문제는 선제진 사이에서 난이도를 오판해서 G정도의 포지션에 들어갈 예정의 문제였다...본인은 regions trick을 이미 아는 상태였어서 이걸 실제로 발상하는 난이도가 얼마인지 잘 몰랐고, flappybird가 다이아정도의 문제일 것이라고 예측해서 나도 regions와 비슷한 난이도겠거니 생각해서 G정도에 넣었다. 그런데 검수진들의 의견을 들어보니 이런 아이디어가 그렇게까지 어려운 발상은 아니라는듯해 보여서 E에 넣었다. 다른 이슈로는, 문제가 살짝 티피컬하지 않느냐는 의견이 있긴 했었다. 그런데 애초에 이미 셋에 인터랙티브/투스텝/구성적이 거의 대여섯개씩(...) 있는 판에 한문제정도는 티피컬한게 있을 필요가 있다고 판단했다... 결과적으로는 꽤 괜찮은 포지션의 문제가 되었다고 (적어도 나는) 생각한다.

 

F. 이 문제같은 경우에는 데이터의 세팅이 꽤 애로사항이었던 것 같은데, 가장 큰 문제는 공선점 판별을 subquadratic하게 하는 것이 어렵다는 점에 있었다. 원래는 10만으로도 돌아가는 솔루션이 존재하지만, 공선점 판별 이슈때문에 그냥 제곱으로 문제를 냈던 것으로 기억한다.

 

G. 이번 대회 세팅의 첫 번째 고비. 인터랙티브 게임이론?과 관련된 문제라고 볼 수 있는데, 일단 기본적으로 백준에서 인터랙티브를 출제하기 위해선 꽤나 까다로운 과정을 거쳐야 한다. 폴리곤에서의 인터랙터 세팅과 백준에서의 인터랙터 세팅이 달라서인데, 그러한 이유때문에 백준님과 상당히 많은 연락을 거치게 되었다... 물론 그것만이 문제는 아니었지만, 일단 대회가 얼마 안 남은 시점에서 인터랙터에 수정사항이 있어도 그게 반영될지 알 수없는건 좀 큰 이슈라고 생각한다. STACK에서 인터랙터를 직접 세팅하는 기능이 추가되기를 바란다... 아무튼, 그뿐만이 아니라 원체 랜덤으로 뚫리기 쉬운 문제라서 인터랙터의 몇가지 전략들을 넣어두긴 했으나, 결국 대회에서 랜덤으로 뚫리는 경우가 간혹 있었어서 완전한 성공은 아니었다. 조금 더 시간이 많았으면 적응적인 인터랙터를 짜는걸 고려해봤을텐데, 적응적 인터랙터를 짤 방법도 잘 모르겠었고 시간도 없었어서 유감스럽게도 비적응적 인터랙터로 대회에 나올 수밖에 없었다.

 

H. 이 문제같은 경우에는 그냥 무난한 느낌의 constructive 문제였기 때문에, 이것도 크게 신경쓰진 않았다. 출제자인 mingyu331이 수 차례 인터랙티브 및 컨스트럭티브 출제경험이 있는것으로 알고 있었기 때문에 크게 걱정되지 않았다.

 

I. 이번 대회 세팅의 최대의 고비. 이 문제는 원래 goodbye 2023/hello 2024의 출제자로 있을 때 우연히 만들어졌는데, 당시에는 대회중에 짤 수 있는 사람이 지극히 적을것이라는 이유로 내지는 못하였다. 사실 그 말이 진실로 참이었기 때문에, 1년동안 이 문제를 낼 수 있는 대회를 찾지 못하였고, 사실 세팅하는것도 심각하게 어려울 것이 뻔했기 때문에 출제하는 것이 요원한 상황이었다. 그래서 그냥 이번 대회에 짬처리를 하고자 생각했고, 이를 위해 2월부터 짬짬이 세팅하기 시작했다. 물론, 이는 무척이나 까다로운 작업이었다. "투스텝"이면서 "인터랙티브"이며 "스코어링"을 해야하고, 심지어 인터랙터는 기하적인 구현까지 해야했기 때문에 짜야할 것이 여간 많은 것이 아니었다.

세팅을 위해 작성된 코드들의 상상도

일단 인터랙터를 작성하는데에만 12000바이트를 짰고, 애초에 정해도 12000바이트이다. 인터랙터는 각 직선들의 교점을 fraction class를 이용해서 구하고, 이러한 정보와 유니온 파인드를 사용해서 존재하는 모든 구역을 찾고, 이들을 enumerate하고, 그 뒤 해당 그래프 위에서 인터랙션을 진행한다. 모든 구역을 찾는 코드만 거의 300줄이었던 것으로 기억한다. 사실 정해도 우여곡절이 많았는데, 원래는 M=147로 낼 생각이었으나 풀이가 터져서 고치는 도중 55가 되고, 그 풀이마저 터지며(...) 추가적인 최적화를 거친 끝에 28이라는 값에 도달하게 되었다(문제를 해결하신 분들을 보면 28보다 훨씬 적은 값으로도 풀리는듯하나, 사실 적당한 개수로 된된다면 그걸로 충분하다고 생각했다). 아무튼 기초세팅만 해도 심각한 애로사항이 있었고, 검수과정에서도 솔루션이 잘 작동하지 않거나 인터랙션이 잘못되는등 여러 이슈들이 있었고, 지문도 여러번 갈아엎게 되었다. 백준님과 소통해서 스택에 문제를 세팅하는것도 큰 애로사항이었는데, 이것도 어떻게든 결국 성공하긴 했다.

 

2.1. 본인이 출제한 문제별 출제 후기

B. 문제가 부족해서 적당히 만든것 치고는 꽤 괜찮은 문제였다고 생각한다.

 

G. 원래 이 문제는 평소에 아이디어를 쌓아두고 임의의 올림피아드 콜포태에 던져볼 작정으로 포뮬레이션을 구상하고 문제를 만들기 시작했었다. 이하는 문제에 대한 스포일러가 될 수 있다.

처음에는 답이 2n-3 미만인 충분히 좋은 전략이 존재할 것이라 생각하여 열심히 생각해보았지만, 마땅한 결론을 도출해내지못하였다. 그래서 n=4에 대해 브루트포스 시뮬레이션을 돌려보았는데, 놀랍게도 m=5가 나오는 것을 확인했었다. 그래서 2n-3이 한계인지 생각해보았는데, 어떤 auxiliary graph를 만들어서 그걸 실제로 증명할 수 있으며, 그 전략을 exploit하는것도 가능하다는걸 발견해서 무척 신기했었다.

아무튼 해당 문제를 만들고나서 수올 콜포태에 넣을지 고민했었는데, 그러기엔 문제가 노잼이라는 평을 듣고 그냥 EGOI에 내려했지만, EGOI 콜포태 데드라인까지 세팅을 못끝내서 그냥 짬처리하기로 했다. 사실 이때까지만 해도 문제가 별로 재미없나싶었는데, 검수진들이나 문제를 풀어본 사람들 평을 보면 그냥 역시 OI 콜포태에 내는게 나았나싶긴 했다...

 

I. 해당 문제는 강력한 모티베이션을 가지고 "구성"되었다. https://www.acmicpc.net/problem/18847 다음 문제를 다른 class의 그래프에 대해 돌릴 수 있지는 않은지에 대해 생각해본 것이 이 문제의 시초였다고 볼 수 있다. 해당 문제는 트리 위에서 2-coloring을 줘서 어딘가로 이동하는 적절한 전략을 구성하는 문제인데, 이것이 다른 그래프에 대해서 잘 풀리지는 않는지에 대해 고민해보았다. 그러다가, 예전에 수올판에서 가끔가다 몇개의 직선으로 구분되는 구역들에 관한 문제가 떠올라서 해당 그래프에서 문제가 풀리는지 고민해보았고, 그 결과 생각보다 문제가 꽤 괜찮게 풀린다는걸 발견했다.

 

그러나 역시 구현이 형언할 수 없을 정도로 복잡하게 될 것임이 분명했기 때문에 아이디어로만 1년동안 묵혀두다가, 이번 기회에 출제하게 된 것이다.

 

개인적으로 본인이 출제한 문제중 가장 "좋은 문제"와 가장 "신기한 문제", 가장 "깔끔한 문제"같은걸 자주 생각해보는 편인데, 이 문제는 가장 신기한 문제에 속하는 것 같다. 암튼 이 문제가 결국 세상에 공개되어서 다행이라는 생각이다.

 

3. 온사이트 대회

아무튼 세팅이 적절히 끝나고 여러 검수자분들의 검수를 거쳐서 대회 당일이 되었다. 사실 대회 당일에도 부회장이 제주도로 여행을 떠나서 현장 운영진이 줄어들어 이것도 적잖게 애로사항이었다.

 

H의 체커가 잘못되어 뚫리거나, 몇몇 문제에서 살짝 문제가 발생하긴 했지만 결과적으로 큰 이슈로 번진 것은 없었고, 아무튼 대회가 잘 마무리되었다.

 

대회 슼보의 상상도

대회슼보는 대략적으로 다음과 같았다. 아래에도 물론 사람이 있지만, 이걸 전부 다 붙여넣기에는 귀찮기 때문에 윗부분만 올린다. 대충 솔브수가 굉장히 선형적으로 변화해서 나름 밸런스있는 셋이었다고 생각한다.

 

이후에는 대략적으로 풀이를 설명하고, 슼보를 깐 뒤 뒷풀이를 진행했다. 뒷풀이는 우마이에서 진행되었는데, 우마이의 터무니없이 느린 회전율때문에 중간에 몇몇 인원들과 탈주해서 치킨을 쌀먹했다. 생각해보니 아직도 치킨 정산을 올리지 않아서 이걸 좀 올려야할거같다.

 

암튼 그 뒤로 오락실에 가서 츄니즘을 적당히 쌀먹하고 끝났던 것 같다.

 

4. Open Contest

오픈콘테스트는 별 차질 없이 진행되었고, 결과는 다음과 같다. 사실 당일에 내가 토익을 쳤기 때문에 크게 신경쓸 겨를이 없었다.

 

 

5. 소감

굉장히 우여곡절이 많게 열린 대회였어서 대회의 핵심 운영진이 되는 것이 얼마나 힘든 일인지 깨달을 수 있는 경험이었다. 역시 투스텝을 출제하는건 극심한 고통을 수반한다는 것 또한 오랜만에 깨달을 수 있었다. 그와는 별개로, 어디에 낼지 고민이었던 문제 두개를 투척해서 셋이 갓셋이 된거같아서 꽤 괜찮게 딜을 봤다고 생각한다. 다음 대회는 조금 더 빨리 준비할 필요가 있음을 깨달았다...