[24/09/09] 제5회 고려대학교 MatKor Cup: 2024 Summer/Fall 후기

저번 MatKor Cup(4회)에서는 검수진으로 참여했었고, 11문제를 검수했었다.

따로 검수 후기를 적지 않았었는데 간단하게 적어보고, 이번에 열렸던 MatKor Cup에 대한 검수 및 운영 후기를 적어보고자 한다.

 

저번 맷코컵에서는 예비 소집 문제 4문제 + 본 대회 문제 5문제에 대한 정해를 작성하고, 본 대회 2문제에 대한 서브태스크 코드를 작성함으로써 11문제를 검수했다. 사실 이때는 검수에 많이 익숙하지 않았던 터였고, "검수 == 정해짜기"라고 생각했던 터여서, 에지 케이스를 생각한다던지 대회장에서 나올 수 있는 WA코드들을 낸다던지 등의 소위 말하는 "제대로 된" 검수를 하지 않았었다. 그때 당시의 나는 열심히 검수했다고 생각했지만, 지금 생각해보니... 암튼 그렇다.

 

이번 맷코컵에는 본 대회 A번을 출제했다. 더불어 7문제에 대한 정해를 작성 + 데이터 검수 및 WA코드 저격 등을 했으며 한 문제에 대한 서브테스크 코드를 작성했다.(이 문제는 정해는 작성하지 않았고 데이터 검수도 따로 하지 않았다.)

즉, PA, PB, PC, PD, B, C, D를 검수, A번을 출제했다.(예비 소집 4문제 + 본 대회 4문제)

지금 이 글을 작성하고 있을 당시에는 문제가 올라오진 않았지만, "현대모비스 첨단 운전자 보조 시스템"이라는 제목으로 문제가 올라갈 예정일 것이다. 막 올라왔다. 많이 풀어주셨으면....

 

A번 문제의 아이디어는 다음과 같은 문제에서 시작되었다.

https://www.acmicpc.net/problem/2710

삼각형 정원이라는 문제인데, 이 문제를 처음 해결한 때는 2022년 6월 28일, 즉, 지금으로부터 2년 이전의 시간이었다.

해결했을 당시에는 나 제외하여 2명만 해결한 상태였고, 난이도도 "골드"로 매겨져있었다. (지금은 플레3으로 올라갔다.)

삼각형의 좌표가 주어질 때, 그 삼각형의 각 변의 중점에 내접하는 내접 타원의 초점과 장축의 길이를 물어보는 문제이다.

처음 보고 충격과 공포를 먹었고, 검색해보니 "슈타이너 내접 타원"이라고 이름이 붙여져 있을 만큼 나름? 알려진 내용이었다.

슈타이너 내접 타원의 초점은 "마든 정리"를 통해 구할 수 있다. 이 정리는 삼각형을 복소평면으로 옮기고, 그 점을 근으로 가지는 다항식의 도함수의 근이 슈타이너 내접 타원의 초점이라는 정리이다.

물론 이러한 내용을 검색해서 해결했었고, 해결했었을 당시에는 굉장히 신선한 충격을 받았었다. 정리는 선형대수적 지식 + 복소해석학적 지식을 사용하여 증명한다.

 

맷코컵 문제 출제 시기가 다가오고, 이전에 이런 좋은 인상을 받았었던 문제가 있었기 때문에, 마든 정리를 확장 혹은 활용하는 내용의 문제를 내고자 했었다.

문제의 상황 자체는 현재와 거의 비슷한데, 내접 타원의 넓이의 합의 최솟값을 구하는 것이 초기 버전이었다. (이때 당시에는 마든 정리를 사용해서 구하는 것이 의도였다.)

하지만, 삼각형 정원 문제의 너무나 사소한 변형인 것 같아 내접 타원의 넓이의 합이 아닌, 내접 타원으로 둘러싸인 넓이의 최솟값을 구하는 것으로 바꾸었다.

그림을 그려보니 꽃모양처럼 생겼었고, 초기 가제도 Flower이라는 이름이었다.

따라서 처음에 생각했었던 풀이는 1. 마든 정리를 통해 타원의 초점을 구하고, 2. 이를 통해 타원의 방정식을 구하고, 3. 중심에서 주어진 구역을 직접 적분하여, 4. 그 영역들을 전부 더하여 삼분탐색을 하는 풀이었다. (이때 당시만 해도 넓이가 일정하다는 사실을 깨닫지 못한 때였다.)

Convex하다는 것은 쉽게 보이니, 삼분탐색을 하면 충분할 것이라고 생각했다.

 

근데 막상 구현하려니 좀 어려웠고, 이 문제를 해결할 좋은 아이디어가 없을까 하다가 문제를 다른 운영진 분들에게 공유했었다.

이때, yjiw0930님께서 뭔가 일정할 것 같다는 이야기를 해주셨다. 곰곰히 생각해보니 뭔가 일정할 것 같았고, 실제로 위키백과에서도 슈타이너 내접타원의 넓이가 삼각형 넓이의 일정한 배율이라고 나와있다는 것을 확인. 이후, 왜 일정한 배율인가에 대해 찾아보니 아핀변환의 특성때문이라는 사실을 발견했다.

마찬가지 이유로 내접타원으로 둘러싸인 넓이도 다각형 넓이의 일정한 배율이 될 것이라는 사실을 확신했고, 금방 증명까지 했다.

 

근데 이 문제 세팅을 시작할 때 즈음, 문제를 더 어렵게 만들고자 하는 맷코의 전통? 의지? 근성? 아무튼... 그런 기조에 따라서, 실제로 마든 정리를 사용하여, 타원의 장축의 길이의 합의 최솟값을 구하는 문제로 바꿔볼까 했었으나 세팅이 매우매우매우 귀찮아질 것 같아서 그냥 놔두었다.(참고로 이에 대한 정해는 삼분탐색 혹은 경사하강법으로 생각하고 있었다.)

실제로도 문제 자체도 굉장히 깔끔해져서 만족스러운 상태였기 때문에 그냥 놔두기로 했다.

 

어쨌든, 이후 세팅에 돌입했다. 백준에는 예제가 2개 올라와 있을 것이지만, 처음에는 이러한 사실 때문에 예제를 통해 상수 값을 역추적 할 것 같아서 예제를 하나만 주자고 강력하게 주장했었다. 하지만 정상적인 예제를 주어야 한다는 의견이 강해서, 정상적인 예제를 주는 쪽으로 굳혀졌다.

대신 값을 역추적하기 힘들도록(실수 오차가 발생하기 쉽도록) 굉장히 작은 값을 주는 것으로 이야기가 얼추 마무리 되었다.

 

기하문제를 세팅하는 것은 처음이었기 때문에 조금 생각해야될 부분도 많았다. 처음 문제에서는 좌표제한은 그대로고 점의 개수가 백만개였으나, 이 제한이 볼록 다각형을 만들기에는 터무니없이 힘든 조건이라는 사실을 깨닫고 제한을 1000으로 줄였다.

임의의 랜덤한 볼록다각형을 만드는 방법도 세팅을 하면서 알게 되었다. 내가 랜덤 제너레이터로 만든 데이터들은 N의 제한이 커지면 원에 가까워진다는 단점이 있긴 한데 오히려 그것이 다른 데이터를 짜는데 도움을 주었다.

세팅을 하면서 극단적인 케이스들(예를 들어 엄청 뾰족한 다각형, 각도의 분포가 균일하지 못한 다각형 등)도 세팅해야함을 깨달았다. 다행히, 이건 위의 제너레이터를 조금 수정하여 해결할 수 있었다.

또다른 극단적인 케이스(넓이가 최소인 경우)는 yjiw님께서 도와주셨다. 삼각형부터 팔각형까지 넓이가 최소가 되는 제너레이터를 작성해주셨고 데이터를 추가해주셨다.

 

지문은 현대모비스 후원이 확정되면서 후원사 문제로 적절히 변경되었다. 초기 문제는 꽃받침을 이루는 N개의 점이었고, 구하는 안전영역이 꽃술의 넓이로 서술되어있었다.

 

여기까지가 대충 A번 문제에 관한 이야기였고... 여담으로 이 문제는 다른 검수자분들이 느끼는 난이도 편차가 가장 심했던 문제였다.

나와 같은 수학과(devluyten, kevinlys00) 사람들은 모두 골드(더 나아가서는 실버....라고 주장하긴 했지만 다각형의 넓이 태그 기본 티어가 골드 5였기 때문에 골드라고 바꾸긴 했다)라고 주장하긴 했지만, 이 문제의 아이디어를 처음 받았던 kidw0124님은 플레 상위~다이아를 주장했었고, 다른 분들도 적어도 플레 중위는 된다고 주장했었다.

나는 마든 정리를 보고, 정해의 의도가 바뀌어진 이 문제를 보면서 확실히 마든 정리보다는 현재 아이디어가 훨씬 쉽다고 생각해 골드라고 느껴 그렇게 주장하긴 했다.

어쨌든... 여기까지 A번 문제에 관한 이야기였다.

 

여기서부터는 내가 검수했던 예비소집 4문제 + 본대회 3문제에 대한 이야기를 하고싶다. (모든 과정 속에는 데이터+벨리데이터+제너레이터+체커 확인등의 과정이 포함되었지만 생략했다.)

 

가장 먼저 정해를 짠건 PC였다. 사실 보자마자, 아 이건 너무 너무 뻔한 오일러 피 함수 문제다, 라고 생각했고, 더불어 약간의 맷코스러움을 느꼈다. (kidw0124님은 이런거 좋아하는 것 같다.)

그래서 그냥 예전에 구현했던 오일러 피 함수를 박아넣어서 맞았습니다를 받았다. 검수한 문제 정해 다 짜고 나서 이상한 풀이 통과시켜보려고 어떻게든 비벼봤는데, 단단했다.

 

그다음으로 정해를 짠건 PB였다. 이건 원래 문제가 분수를 출력하는 것이 아니라 모듈로 역원을 곱한 정수값을 출력하는 것이 문제였기 때문에 현재 버전보다 어려운 문제였었다. 관찰을 통해 N/M이라는 사실을 금방 발견하고 짰다. 이 문제도 데이터는 단단했다.

 

그다음에는 B번의 정해를 짰다. 에디토리얼이 안나오긴 했는데, 이건 미분기하학에서 너무나도 너무나도 너무나도 너무나도 유명한 상황이다. 아마 도카르모나 앤드류 프레슬리 책에도 한 단원에 걸쳐 소개되어 있는 내용이고, 공식 하나 딸깍 박아넣으면 풀리는 문제라 그냥 그걸로 해결했다. 궁금한 사람은 Poincare Half Upper plane에서의 Geodesic을 검색해보자.

이 문제를 세팅한 devluyten(aka.박세준)은 반성하길 바란다.

이걸 사용하지 않고도 스넬의 법칙으로 미방 세워서 푸는 풀이가 있다곤 했는데, 나는 그 풀이로 안풀어서 잘 모르겠다. 뭐 어떻게든 풀릴 것 같긴 하다. 나는 저 내용을 알고있어서 딸깍 해서 풀긴 했는데, 그래서 난이도가 좀 체감이 안됬다.

검수하다가 알게 된 점은, 공식 딸깍이면 float정밀도로 뚫린다는 사실이다. 원을 직접 구해서 푸는 방식은 long double정밀도로 해야된다.

 

그 다음은 PA번의 정해를 짰다. 나는 체감 상 플레로 느끼긴 했다. 지오지브라를 통해 실제 그림을 그리고 관찰을 몇시간 동안 한 끝에 해결했다. 식정리도 좀 귀찮아서 더럽다고 느꼈다. 근데 이게 맷코지. 어쨌든 이것도 데이터는 단단했다.

 

그 다음은 D번의 정해를 짰다. 이것도 devluyten이 세팅한 문제인데, 이건 그래도 딸깍 딸깍으로 풀리는 문제가 아니라서 B번보다는 나았다. 해야되는 태스크들이 꽤 뚜렷하고, 세가지 태그가 기어바퀴마냥 하나씩 맞물리는 지점들이 있어서 좋게 느낀 문제였다. 스그문제를 좋아하는 나로써는 하나 배워가는 문제가 되었다. 섭테 1과 섭테 2가 뭔가 약한 데이터가 있는 것 같아서 보강도 했다.

 

이후 PD번의 정해를 짰다. 이건 finimage님이 세팅한 문제인데, 지문이 초기 상태에 비해 많이 수학수학하게 바뀌어서 좋게 느꼈다.(맷코컵의 취지와 어울리고, 수학과로써 만족스럽다.) 데이터도 약한 부분(연결 그래프가 아닌 데이터가 하나만 존재했다.)을 보강했다. 문제 제목은 좀 짜친다. 원래 문제 제목이 A와 B라는 제목이었는데, 이게 훨씬 낫다고 느껴진다. 바뀐 문제 제목은 김동우씨의 취향이 물씬 담겼다.

 

이후 C번의 정해를 짰다. 김동우씨 문제다. 처음엔 문제 해석하는게 힘들긴 했는데, 그부분만 넘기면 쉽게 해결할 수 있는 재미있는 문제이다. 파이썬으로도 꽤 빨리 돌아서, 문제 제한 시간을 낮췄던 것으로 기억한다.(김 동우씨는 파이썬을 싫어한다.)

 

이후 다른 문제 정해를 더 짜보려고, 혹은 검수해보려고 했으나 문제 세개는 검수진 추정 난이도가 루비였고, 나머지들은 다이아, 그리고 내가 약한 확률여서 그만뒀다. 시간이 없기도 했고... 마지막으로 해보려고 했던건 P번이었는데, 섭테만 짜고 멈췄다.(정해는 못짰다. 섭테는 그냥 BFS여서 금방 했다.)

 

이번 맷코컵은 저번 맷코컵에 비해서 확실히 문제들이 어려웠다. 저번에는 그래도 실버, 브론즈가 존재했는데 이번에는 그것 마저도 없으니... 참담할 뿐이다. 맷코컵에 참여한 사람들이 열심히 5시간동안 움직이는 모습을 보며 조금 안타까움을 느꼈다. 맷코컵에 참여하는 사람은 마음을 단단하게 먹어야 할 듯 하다. (그 전에 맷코컵이 오래 유지가 될지에 대한 의문이 있기도 하다...)

 

대회 당일 날은 사실 깊이 기억나진 않는다. 왜냐면 검수와 출제는 한달동안 내내 했었고 대회는 하루였기 때문에... 그렇지만 항상 재밌게 느끼는 점들은 스코어보드와 다른 사람 코드 구경이다. 대회때는 기상천외한 코드들이 많이 나온다.

스코어보드도 업치락 뒷치락 하며 올라가는 모습이 재밌다. 대회 끝나고 마무리로 회식한 것도 좋았다.(i love util) 회식비를 쾌척해주신 유틸님께 감사함을 느낀다. 

 

어쨌든, 출제와 검수하면서 많은 것을 배워가서 좋은 경험이었다. 다음엔 난이도를 쪼끔만(ㅎㅎ) 낮춰서 했으면 좋을 것 같다..ㅋㅋ