현대모비스 본선 / UCPC 2023 후기

그냥 아카이빙 목적으로 짧게 씁니다.

현대모비스 본선 대회

본인은 2021년 대회에서 8등인지 9등인지 했고, 2022년 대회에서 예선 탈락을 해서, 2023년 대회 참가가 가능했다.

1번을 열었는데 딱 봐도 따져야 할게 많아 보여서 힘들어 보였다. 따져야 할 걸 안 따지는 풀이를 짜니 10.2/15점이 나왔다. 일단 뒤로 넘어간 다음에, 뒤쪽 문제에서 주는 점수 기댓값이 4.8 미만일 때 돌아오기로 했다.

2번 뭔가 잘 안 읽혀서 뇌절하다가 대충 간선 하나 빼고 dag 경로 없는지 체크? 로 환원했다. 도미네이터 트리로 "풀 수는 있다" 는 것을 알았다. 더 생각해서 간단하게 만들 수도 있겠지만, 그냥 짤만해 보여서 도미네이터 트리를 짜기로 했다. 일반 그래프의 도미네이터 트리는 굉장히 테크니컬하지만, DAG에서의 도미네이터 트리는 별로 어렵지 않다. 근데 실수해서 디버깅에 시간이 좀 쏠렸다. 아무튼 AC

3번은 SCC를 묶고 path cover 를 찾으면 AC가 나오는 문제로, 대회에서 가장 쉬운 문제라고 생각했다. SCC랑 매칭을 직접 짜 본지 오래되었지만, SCC는 그냥 floyd-warshall로 구하면 짧고, 매칭은 다시 생각하려고 하니 생각이 났다. AC

그리고 대충 1시간이 조금 안 되어서 프리즈가 되었다.

4번을 읽었다. 몇가지 typical한 단순화를 거치면 아주 거대한 구현 문제가 되고, 더 고민해서 그냥 어찌저찌 짤 수는 있는 정도로 줄였다. 대회 format이 제출을 많이 해도 페널티가 없는 형식이라 좋았다. 그래서 적당히 느린 알고리즘을 짜고, 계속 제출하며 정확성을 유지한다음, 알고리즘을 최적화하는 식으로 할 수 있었다. 4번 문제의 풀이를 여쭤본 분들이 많았는데, 대충 이런 식으로 하면 된다.

• 45도 회전을 했을 때, (x, y) 좌표의 기우성이 같은 점의 개수를 세면 된다.
• 좌표 압축을 한 후 인접한 좌표로 압축된 직사각형을 "Atomic rectangle" 이라 하자. 이러한 것의 개수는 $O(N^2)$ 개이다.
• 마름모와 교집합을 취해줘야 하는데, two pointer처럼 생각하면 $O(N)$ 개의 직사각형은 마름모와 부분적으로 겹치고, 나머지는 아예 밖이거나 아예 안이다.
• 짤 수 있기 위해서는 마름모의 네 변 케이스를 무조건 독립으로 만든 다음 따로 구현해야 한다. 마름모를 잡고 계속 교집합으로 하는 식으로는 할 수 없다고 생각한다. 각 변에 따라서 짤리는 마름모 선이 독립적으로 나오게 한 다음에 전체 - (/ 선의 위쪽) - (\ 선의 위쪽) - ... 처럼 하게 해야 한다. 이러려면 네 변의 케이스를 무조건 따로 분석해야 하고, 그냥 많은 단순 계산을 해야 한다.
• 이렇게 하면 이제 $O(N^2)$ 가 된다. 아예 안인 직사각형이 구간을 이루기 때문에, 이 구간을 이분 탐색으로 찾아주고, 이 안 계산을 세그먼트 트리로 최적화하면 $O(N \log N)$ 이 된다.

한 90분동안 계산기가 되어서 식을 열심히 계산했고, 대회가 30분 남았을 때 $O(N^2)$ 풀이 (18점), 대회가 8분 남았을 때 $O(N \log N)$ 풀이 (AC) 가 나왔다. 대회는 8분이 남았고, 남은 시간 1번을 별로 안 열심히 시도했고, 95.2점으로 대회가 끝났다.

대회가 끝나고 현실적으로 4번을 푼 사람이 없을 것 같다고 생각했지만 뭔가 걱정이 되었다. 다행이도 기우였고 4번을 다항 시간에 푼 사람은 없어서 학생부 1등으로 마무리했다. 2022년 대회도 1등상 규모가 거대했는데 2023년 대회의 1등상 규모는 더 커졌다 (4000만원 가량). 구름이 여기까지 내다봐 준 것일까? 작년 대회를 운영해준 goorm.io 에 감사의 말씀을 드린다.

차는 내년 2월에 받는데 이 시점 미국 유학으로 인하여 한국에 없을 것이 확실시 되어서, 그 때의 문제는 좀 고민을 해 봐야 할 것 같다.

UCPC 2023

멕시코시티노점상에서타코사먹는윤창기 (주머니에서폰훔쳐가기, 뒷통수치고튀기, 타코뺏어먹기) 팀으로 출전하였다. 실제 팀원은 ainta, koosaga, SongC 이다.

원래 SongC가 아니라 TAMREF 랑 나가려고 했으나, 멕시코로 회사 출장이 있어서 아쉽게도 같이 나가지 못하였다. 급하게 SongC에게 부탁했더니 흔쾌히 받아주어서 현재 팀으로 정해졌다. 팀명은 UCPC 원래 팀을 펑크낸 TAMREF를 괴롭히는 컨셉으로 정했다.

예선은 ainta, SongC가 다 참가하지 못한다고 하여 내가 혼자 짬처리하기로 했었다... 였는데 다행이도 SongC가 중간에 와서 도와줬다. 9문제를 푸는데 2시간 정도 걸렸다. 9문제를 풀고 SongC는 다시 돌아가야 한다 해서 나갔고, 난 E J가 남았는데, J는 풀기 어려워 보이고 E는 고민해 보고 싶지 않아서 그냥 거기서 대회 참가를 종료했다. 그거 말고 딱히 기억나는 건 없다.

팀연습은 한번 했고 NAC 2023를 버추얼로 참가하였다. 10/13 문제 풀고 중간 정도 페널티로 끝났던 것 같다. 이 때 남은 3문제에 대한 코드가 다 있었고 디버깅 할 시간도 각 문제당 1시간 정도 있었는데 셋 중 하나도 맞지 못한게 멘탈 타격이 좀 컸다. SongC가 나머지 두명이 못 푸는 문제들을 괜찮게 풀길래, 팀 밸런스 자체는 괜찮다고 생각했다. 근데 어쨌든 팀원들이 전반적으로 노쇠했기 때문에 (...) 윤교준 팀이 더 잘할 것 같다고 생각했다.

본선 때는 나는 JKLM을 읽었는데 풀 수 있는 게 없었다. SongC가 F를 줬는데 내가 읽은 것 중 그게 제일 쉬워서 (...) 짰다. 첫 AC를 받을 법 했는데 간단한 실수를 고치는데 오래 걸려서 그러진 못했고, 다만 퍼솔로 만족했다.

그 사이에 아마 ainta가 D를 잡고, SongC가 L을 잡았고, 나는 C를 잡고, 셋 다 말렸다. D는 못 고쳤지만, L과 C를 고쳤고 이 때 1시간 좀 지났다. 심하게 말렸다고 생각했는데 4등이기에 기회가 있다고 생각했다.

앞에서 좀 말려서 컴퓨터가 계속 돌아가고 있었기 때문에 생각할 시간이 좀 있었고, 그래서 C를 짜기 전에 A 풀이도 이미 나온 상태였다. 근데 예제가 안 나와서 보니까 풀이가 조금 틀려 있었다. small-to-large 써서 약간 brute하게 고치는 방식을 생각했는데, 다행이도 그렇게 하니까 잘 되었고 이때 4문제. A는 내가 쿼리와 트리 1 을 최근 통신교육에서 수업했던 게 도움이 되었다. 얼마나 도움이 된지는 모르겠지만 하여튼 생각하는 게 훨씬 편해진 건 확실하다.

그 사이에 SongC는 K 풀이를 냈고, 금방 구현해서 맞았다. M을 내가 지문을 이해 못 해서 표류하고 있었는데 ainta가 지문을 이해해 줘서 풀어줬다.

I를 보고 어렵나 싶었는데 다행이도 티피컬한 유형이었고 실수 한번 한 후 맞았다. 이 때 7문제.

이 때 남은 문제는

• EH: 하기는 싫지만 안 어려워 보이는 문제
• BD: ainta가 풀이가 있는데 코딩이 좀 걸리거나 말린 문제
• J: 하기도 싫고 어려워 보이는 문제
• G: ainta가 풀이가 있는데 확실치는 않은 문제

정도로 정리가 되었다. 내가 E를 정리하다 보니까 케이스가 그렇게 많지 않을 것 같다고 생각했는데, 기하는 보통 케이스가 많거나 아니면 내가 케이스를 못찾았거나 (...) 사실 최근에 기하 문제를 풀어본 적이 없고 풀려고 시도한 적도 없어서 피하고 싶었었다. 그래도 어쨌든 7문제 AC 전에 좀 생각해 둔 게 있어서 다음에 하기로 생각했다.

G에 대해서 ainta랑 얘기를 했는데 아주 간단한 풀이가 있고 $O(N^{3/2})$ 바운드를 증명하는 게 쉽다고 알려줬다. 근데 더 빠른 건 모르겠고 $N \le 10^6$ 이라서 자신은 없다고 하였다. 그 얘기를 듣고 그냥 세터 감수성으로 접근했는데, 아주 간단한 $O(N^{3/2})$ 를 낼 수 있는데 $O(N \log N)$ 을 강제하는게 세터 입장에서는 비현실적이다. 내가 출제진이었으면 웬만하면 그 문제를 반려하거나 정 안 되면 $N \le 10^7$ 을 줬을 것 같아서, 그 풀이가 무조건 의도되었을 것이라고 생각했다. 그래서 짜도 된다고 결론을 내렸고, ainta가 짜서 AC. 나중에 $O(N \log N)$ 정해와 동일한 풀이로 결론났다.

E는 내가 정리한 케이스 정도만 해도 맞아서 다행이 쉽게 맞았다. 정말 다행이라고 생각했다. 그리고 좌표 제한이 작아서 convex hull 충돌을 나이브하게 봐도 되는 게 편했다.

H는 손으로 정리해보고 있는데 딱히 좋은 관찰이 안 나오고 기계적인 손 백트래킹만 반복하고 있었다. 그냥 이럴 바에는 컴퓨터로 돌리는 게 안전하고 빠를 거 같아서, 코딩할 문제가 남아있지만 컴퓨터로 백트래킹을 짰고, 규칙 발견 + $a(F(n)) = F(a(n))$ 관찰 정도를 하니 풀렸다. 당시 워낙 많이 풀린 문제여서 그냥 컴퓨터를 썼던 것 같다.

ainta가 B를 좀 전부터 보고 있었는데 프리즈 직후 고쳤고 11문제가 되었다. D는 ainta가 풀이가 있다고 했고, J도 SongC가 어느 정도 느낌이 있다고 얘기를 해 줬다. 나는 그래서 SongC랑 J를 보고 있었는데, 구현하기 상당히 복잡한 풀이여서 정리 및 구현하는 데 오래 걸렸다. 정신 차려보니 코드는 아직 완성이 안 되었고 대회 시간이 20분 정도 남았다. 그래서 급하게 ainta에게 D를 코딩할 시간을 줬는데, 아쉽게도 20분으로는 부족해서 11문제로 끝났다.

나중에 들어보니 J는 우리의 초기 접근이 복잡했고, 이걸 어떻게 줄이면 풀 수는 있을지 몰라도 KMP로 하는 게 훨씬 간단한 문제였다. 그냥 D 믿고 안정적으로 12로 끝내는 게 좋았을 것 같아서 아쉬웠다. 근데 그러거나 말거나 프리즈 이후 타 팀 제출이 다 맞는다고 가정해도 우리 팀이 1등이었다. ㄹㅇㅋㅋ 초반 "지나가는 쉬운 문제" 였던 A와 K가 보스급으로 끝난 게 굉장히 컸던 것 같다.

상품으로는 소니 노캔 헤드셋을 받았다. 사실 내가 쓰던 거랑 동일한 모델이고 대회장에도 갖고 온 헤드셋이었다 (...) 쓰던 건 부모님 드리기로 하고 새 걸로 바꿔 쓰기로 했다. 이후 뒷풀이 하고 해산하고, ainta와 팀 내 최강자를 소환사의 협곡에서 가렸는데 1:2로 패배했다.

주관적인 문제 평가:

• A가 내가 풀었던 것 중에서는 제일 재밌었다. 사심이 없다고는 말 못하지만 20팀한테 풀렸어도 좋은 문제라고 생각한다.
• C도 괜찮았다.
• E H는 내 취향은 아니었던 것 같다.
• F I는 좀 티피컬한 문제였다. E H 비해서는 재밌다고 생각한다. F의 메모리 제한을 64MB로 하려고 했다고 하는데 내가 organizer였으면 나한테 좀 혼났을 것 같다. (선형 메모리 풀이가 DFS에서 터져도 안 이상한 제한이라 그런 세팅은 결코 해서는 안 된다.)
• G도 풀이가 재밌다고 생각하는데 약간 찍어 맞추는 건 별로일지도? 최소한 이론상으로는 재미있는 문제라고 생각한다.
• J는 대회 때 정말 별로라고 생각했는데 정해는 우리 생각보다 훨씬 깔끔하게 접근했던 것 같다. 정해를 정확하게 알지는 모르지만 부분합을 string matching으로 표현하는 건 이미 알고 있던 아이디어라 내가 반성해야겠다는 생각이 들게 하는 문제였다. 30팀까진 아니어도 med-hard 정도로 볼만했다고 생각한다.
• 안 쓴 문제는 문제를 모름

What's next?

9월부터 MIT의 Mohsen Ghaffari 교수님 밑에서 Distributed Algorithm을 공부하기로 하였습니다. 따라서 한국에 있는 것은 이번 1달이 마지막이고, 올해 SCPC 역시 일정상 참가하지 않습니다. 최근에 PS를 하면서 얻는 지적 자극이 옛날 같지 않아 고민이었는데, 적절한 때 좋은 기회를 얻어서 운이 좋다고 생각합니다. PS를 접을 생각은 없으나 그래도 전보다는 조금 뜸해지지 않을까 싶습니다. 재미있는 이야기가 있으면 꾸준히 블로그를 들리겠습니다.