UCPC 2022

상위권 팀에 대해서 아는 정도만 적으면

• 초비상!!: koosaga, tlwpdus, khsoo01
• 우리가 우승할 수 있을 리 없잖아, 무리무리!: UCPC 2021 디펜딩 챔피언, 2020/2021 서울 리저널 챔피언 FSM (서울대, WF 규정에 따라서 올해 리저널 출전 가능할 수 있음)
• BabyPenguin: 2021 서울 리저널 BabyPenguin (KAIST, 올해 리저널 출전 가능)
• 🐟🐚🦂: cubelover, alex9801, kajebiii
• UCPC의 최신 동향: arnold518, karuna, blackking26 (서울대, 올해 리저널 출전 가능)
• DM 확인 부탁드립니다! 🙏: 2019/2020 서울 리저널 Ternion
• aHR0cDovL2Vyci5vLXIua3Iv: Lawali, leecs0503, stonejjun (고려대, 올해 리저널 출전 가능)
• Rinjinbu_SSHS: 이것도 아인타가 있는 것만 알고 있다. 본인 학교 친구들로 알고 있음
• 예일대: kdh9949와 군대 선임 분들의 팀이라고 들었다. IMO 금메달이 있는 평범한 선임 분들... (서울대, 올해 리저널 출전 가능)

별로 신뢰도는 없으니, 그냥 내가 알기로는 그렇다~ 정도로 받아들이면 좋을 것 같다.

팀 결성

팀은 원래 별 생각 없었는데 정신차려보니까 사람들이 너도나도 팀을 구하고 있기에.. 급하게 SOS를 쳐서 빠르게 구했다.

팀명은 이렇게 정했다.

팀명은 쵸비와는 무관하다. 대회 때 페이커 유니폼을 들고 온 사람이 있었다. 무슨 팀이라고는 말하지 않겠다. 관계없는 둘을 엮으려는 악질적인 시도로 보이지만... 1등으로 쇼앤프룹했다.

예선

낙성대쪽 스터디룸에서 모여서 했다.

C, I 빼고는 그냥 각자 정신없이 풀었던 것 같고, 잘 기억 안 난다.

C는 처음에 보고 잘 생각이 안 났는데, 바텀업으로 그리디하게 될 것 같아서 내가 풀었다. 재밌었던 문제.

I는 서로 브레인스토밍을 하다가, 답에 적당한 상한이 있을 거 같고 Construction이 될 것 같다는 결론에 도달했다. 꽤 그럴듯 했고 증명이 될듯 말듯 하다가 시제연이 던진 "오일러 투어" 한마디에 혈이 뚫렸다. 정확히 누가 무슨 아이디어를 냈는지는 기억이 안 나는데, 누가 짤래 하니까 팀원들이 날 물끄러미 쳐다봤다 (나쁜놈들..). 내가 짰으니까 내가 푼 문제이다.

나중에 보니까 I는 IOI 2016에 비슷한 문제가 있었던 것 같다. 대회 중에는 전혀 기억 안 났다. IOI 대회때는 건들지도 못 했던 문제인데, 지금 다시 보니까 쉬운 것 같아서, 나름 성장했다는 느낌을 받아서 좋았다.

대회 끝나고 문제 복기까지 간단히 했는데 4시도 안 돼서, 저녁 식사 없이 해산했다. 프리즈 전에는 1등을 못 하겠다고 생각했는데, 나중에 확인해 보니 꽤 큰 차이로 1등으로 마무리했다.

팀연습

다들 바쁜 사람들이라서 안 할까도 싶었는데, 1컴 온사이트가 3년만이라서 환경 적응을 꼭 해야 할 것 같다고 생각했다. 그래서 NERC 2021로 팀연습을 했다.

• C, D는 내가 대충 밀었다.
• I를 현수가 해석을 잘못해서 줬다. 그래서 다른 문제를 풀고, 틀리고, 문제가 다름을 깨닫고, 현수를 돌리고, 다시 풀어서 맞았다.
• 그 사이에 L, J, F, E를 팀원들이 풀었다.
• 나는 K를 풀었다.
• 내가 G 짤 사람을 열심히 모아봤지만 아무도 하고 싶어 하지 않았다. 그래서 내가 짰다. 진짜 나쁜 사람들
• G의 코드는 금방 나왔는데 WA가 나왔다. 그런데 아무리 봐도 맞는 코드라서, 손대고 싶어도 손댈 부분이 없었다. 한 시간 넘게 보다가, 체념한 채로 double을 long double로 바꿨고, 맞았다. (돌이켜보면, subtraction 때문에 실수 오차가 문제가 되는 게 맞다. 이 생각을 못한 건 명백히 내 실수)
• 나랑 현수가 같이 H를 잡고 시제연이 B를 잡았다. B는 시제연이 맞아줬고, H는 열심히 고민했지만 견적이 안 나와서 못 풀었다. 돌아보면 H는 뭘 해도 못 푸는 문제였고, A를 잡는게 나았을 것 같기는 한데, 뭐 그런걸 항상 정확히 알 수는 없다.

끝나고 보니 K를 푼 팀이 매우 적었다. 솔직히 개 쉽고, 기억도 안 나는 문제였는데, 결과가 이렇게 나와서 좋았다. 이럴 때가 재밌다. 스코어보드 전체적으로도 결과가 예상한 것 이상으로 너무 좋았다.

이후 적당히 저녁먹고 해산했다. 재밌어서 한번 더 하고 싶었지만, 팀원들은 나처럼 백수가 아니었다. 진짜 물리적으로 시간이 없음을 깨닫고, 본선 때 다시 보기로 했다.

본선

본선 대회 시간이 11시였다. 평소에 기상하는 시간인데... 하여튼 졸린 몸을 이끌고 대회를 시작했다.

나쁜 놈들이 쉬운거 밀어달라고 날 컴퓨터 있는 자리에 앉혔다. 하지만 A, B, C, D 중에서 쉬워 보이는 게 없었고, 노약자석으로 돌아갔다.

그러다가 I가 내 손에 들어왔는데, 그냥 단순 웰노운 자료구조 문제라고 생각했다. 코딩했고 WA.

I를 고치는 방법이 잘 안 보여서, 시간 남을때 D를 짜서 맞았다.

그리고 좀 더 고민하다가, 그냥 근본적으로 I를 내가 너무 대충 생각했고, 간과한 부분이 너무 많다는 것을 깨달았다. 풀이가 아예 회생불가능이라고 판단했고, 뭐 어떻게 풀어야 할지 잘 모르겠어서 시제연한테 넘겼다. 그 이후 E를 좀 봤다.

시제연이 생각보다 금방 풀이를 냈는데, 내가 처음에 짠 웰노운 자료구조 코드를 기반으로 빨리 짤 수 있을 것 같아서 I를 맞았다. 그 때가 대회 시작 140분.

그리고 난 E의 깊은 심연 속으로 들어갔다. 진짜 트롤이 아니고 난 정말 E가 풀고 가야 하는 문제라고 생각했고, 할게 없어서 좀 일찍 시작했다. 뭐 팀원들이 엄청 바쁜 상황도 아니었어서... Max Flow / Min Cut LP의 Dual을 취하면 저런 식의 퍼텐셜 차와 관련된 식이 나온다. 그래서 문제 자체는 LP Duality로 접근하는 게 맞다고 생각해서 그 쪽으로 계속 접근했다.

Duality를 해 보면 알겠지만 이게 행렬식을 꼼꼼하게 반전시켜야 해서 쉽지 않다. 문제 자체의 디테일도 중간에 많이 놓쳤고 (음수 부분의 처리가 말끔하지 않았다) 그냥 다 떠나서 계산을 미친듯이 절었다. 정말 같은 LP만 한 다섯 번 이상 듀얼을 처음부터 취했고 매번 다른 결과가 나왔던 것 같다. 좀 계산을 잘 했으면 좋았을 텐데..

그러다 한 4시간 정도가 되었고, 이제는 듀얼이 진짜진짜최종무조건맞는 정의라고 생각해서, 코드를 짜기 시작했다. 대충 $V = N, E = N^2$ 정도의 그래프에서 $\log (10^{14})$ 번 플로우를 구하는 식의 코드였다. 이 문제는 일단 Circulation 문제로 푸는 게 편했고, 그래프가 디닉이 안 돌 사이즈인거 같아서 Push-Relabel을 사용했다. 문제는

• 예제가 안 나왔다
• 그래프를 손으로 그려보고 실제로 플로우를 흘려도 예제가 안 나왔다
• 근데 코드에서 안 나온 방식과 예제가 안 나온 방식이 달랐다
• 예제를 나와도 저 코드가 시간 안에 돌 것 같지가 않았다

였다. 저 쯤에서 난 "코드도 잘못 짰으며 모델링도 여전히 틀렸다" 라는 결론을 내렸고

• LP에서 실수한 부분을 고쳤고
• 듀얼 또 취하고 (또 한번 아예 다른 모델링이 나왔다..)
• 베꼈던 200줄짜리 푸시 리라벨에서 오타 한 글자를 찾았다 (!)

그리고 예제가 나왔고, 제출하고 TLE를 받았다. 예상대로 최적화가 필요했었고, 그래서 최적화 작업에 들어갔다. 처음에는 MCMF 쪽으로 좀 생각을 하다가, MCMF도 비슷하게 느릴 거 같아서 포기했다. 그러다 잘 생각해보니까, 이 문제가 최대화하는 게 Circulation 상에서 어떠한 간선 하나의 유량이고, 그러면 이는 그냥 최대 유량 문제로 볼 수 있다는 결론을 내렸다. 그래서 이 관찰을 사용해서 시간 복잡도를 $O(N^3)$ 으로 줄이고 4시간 51분에 AC.

그래서 결론적으로 대회 후반부에 무지성으로 E만 잡았지만 (G에서 SOS DP 가 필요하다고 해서 그걸 중간에 도와주긴 했다) 그 사이에 팀원들이 잘 캐리해줘서 우승했다. 처음 시작할 때는 버스 타겠다고 날 컴퓨터 자리에 앉혔지만, 결국 버스 운전해주는 팀원들의 츤데레함에 감동했다.

팀원들이 B를 거의 푼 것처럼 얘기해서 난 12문제로 안정적인 문제차 우승을 할 거라고 생각했다. 하지만 B를 좀 늦게 시작한 면이 있어서, 결국 풀지 못했고 결국 11문제로 마무리했다. 그래도 1등으로 끝날 거라고 생각했고, 실제로 그렇게 되었다.

끝나고 몇 팀 모아서 뒷풀이 후 해산했다. 사진은 아쉽게도 찍지 못했다.

결론

오랜만에 온사이트 대회 해서 정말 재밌었다. UCPC 최고~