SUAPC 2024 summer 3등 후기 (탈PS는지능순)

Without Spoiler

아직 오픈 콘테스트가 시작되지 않아서, 지금 여기에 적을 수 있는 것만 적어 보려고 한다. 예를 들어서 팀 결성에 관한 이야기라던가, 수상자들에 관한 이야기라던가. 우리 팀이 무슨 문제를 풀었는지, 내가 무슨 문제를 풀었는지에 대해서는 물론이고 1등이 몇 문제를 풀었는지도 공개하지 않을 생각이다. 그렇게까지 해서 이런 후기를 적는 이유가 무엇이냐. 이번 SUAPC는 좀 이변과 할 말이 많은 대회였기 때문이다. 최소한 나에게는.

자기실현적 예언? 2

8대 플래티넘 : 6대 플래티넘은 며칠 전에 땄지만 8대는 못 땄다. 아직 그리디가 50점 가량 부족하다. 내가 그렇게 욕심이 많은 사람이 아니라서 그리디에 약한 걸지도 모르겠다. 우리는 이것을 실력 이슈와 비겁한 변명이라고 한다.

이분탐색 공부 : 어느 정도 한 것 같다. 아닌가? 아직 부족한 것 같기는 하다.

10등 안에 : 들었다. 무려 3등이다!!

 

CodeForces는 추하게 1600점을 찍고 거의 방치하듯이 놔 두고 있고, AtCoder도 최근 복귀하고 1300점에 세우기 전까지는 3개월 정도 방치해 둔 것 같다. 백준 대회도 많이 없어지고, 본선은 갈 거라고 열심히 준비했던 UCPC는 예선에서 마감했으며, OnlineMathContest라고 코딩보다 더한 관심사가 근래 급부상해서 코딩은 하는 듯 마는 듯 했다. 이런 상태에서 SUAPC가 곧 열린다고 며칠간 몇 문제 풀기는 했지만 공백이 좀 있었다. 수상은 초고수 dreami63이 있어서 가능할 거라고 생각했지만 이렇게 높은 위치에 오를 수 있을 거라고는 생각을 못 했다.

원래는 kiwiyou와 dreami63, 그리고 내가 ICPC 팀을 결성했다. 나와 dreami63은 나이로 인해서 작년 혹은 올해가 마지막 ICPC인 게 확정이고, kiwiyou도 PS와 슬슬 멀어지고 있어서 마지막을 화려하게 불태우며 대학생으로서의 PS를 마무리지을 심산이었다. 그리고 그 전초전으로서 SUAPC를 고르고 내가 톡방에 출전 의사를 타진했는데...

kiwiyou.run

kiwiyou << 이 사람이 운영진으로 도망쳤다!! 버스 두 대 사이에 끼여 열심히 달리는 승용차가 되기 위해서 나름 연습도 하고 있었는데 계획이 예상치 못한 방향으로 틀어졌다. 작년 여름에 출제진으로 도망치며 :blobdead:팀이 흩어지게 된 전적이 있으니 그 업보다 생각하고 있지만...

1인, 혹은 2인 1팀으로 신청 후 신촌 연합 측에서 랜덤 매칭을 성사시켜 주는 방안으로도 팀 구성이 진행되고 있으나 아무래도 같은 학교 세 명이 팀을 맺는 것이 그림으로서는 좋았다. 일단 모일 장소가 학교 안의 동방으로 확정되는 것부터가 여러모로 편하니까. 그래서 저번 SUAPC처럼 동아리에서 사람을 한 명 데려오기로 하고 팀원 구인 게시판에 글을 올렸지만 반응이 없었다. 사실 아직도 없다. 왜 그럴까...

엄청난 고수 now_cow를 붙잡아 와서 구멍 하나가 있지만 엄청나게 강력한 팀을 만들어 보려고 했지만 대회 시간에 외국에 있다고 고사했다. 하지만 이 사람은 결국 SUAPC에 참가해서 수상을 하게 되는데... 이 이야기는 조금 있다 공개됩니다.

 

ChatGpt - Most weird method to determine something

결국 dreami63이 마지막 퍼즐을 잡아 왔다. 그 뒤로는 조금 느릿하지만 착실하게 진행이 됐다. 팀명을 정하고, 신청을 하고, 중간에 닉네임을 내가 잘못 적어서 신촌 연합 회장인 ez_on을 통한 루트로 닉네임 수정을 하고... 이래서 능지처참인가?

그런데 이 닉네임이 스코어보드에 안 올라서 PS대회를 하면서도 탈PS는지능순이라고 외치는 미친 어그로를 끌어버렸다. 내 닉네임인 능지처참까지 올라갔어야 어그로력이 좀 덜했을 텐데 왜 이렇게 됐을까. 이런 것을 예상하지 못했기에 정말 능지처참 아닐까? 어라, 이거 잘 지은 닉네임...?

그런데 대회 얼마 전, 팀원이 피치 못할 사정으로 참여가 불가능하게 되어 버렸다. 대타까지 모시고 왔지만 대회 운영진 내부 회의 결과 이미 신청한 인원의 변경이 불가능했고, 그냥 두 명이서 대회를 치르게 되었다. 2인팀의 탄생이었다.

 

1, 3, 4, 8등 팀이 연세대 팀이다. 항상 SUAPC는 스코어보드의 최정상에 연세대와 서강대의 혈투가 벌어지는데다가, 서강대에서도 강력한 팀 셋이 출전한다고 해서 3등 안에 드는 건 애초에 고려 대상이 아니었는데, 3등을 어째 성공해 버리고 말았다.

1등 팀 PS:Endgame (Serendipity__, plast, JYJin)은 진짜 엄청난 실력의 팀이다. 연세대의 현재 유이한 레드가 다 저 팀 안에 있고, 세 팀 모두 베트남의 ICPC Asia Championship을 경험하고 온 사람이다. ICPC WF에 가장 가까운 연세대학교 사람이 아닐까. SUAPC에서 1등 자리를 차지하느냐 마느냐의 싸움을 하고 있는 괴물들이다. 이번 대회에서도 역시 단 1초도 스코어보드 꼭대기에서 내려 온 적이 없이 Redshift와 저세상 싸움을 하고 있었다.

2등 팀 Redshift (shiftpsh, Vermeil, 1bin)도 엄청난 실력의 서강대 강호다. 한국에서 PS를 하는 사람이라면 이제는 모를 수가 없는 solved.ac의 개발자 shiftpsh이 포함된 팀. 멤버는 자주 바뀌는데 그럼에도 불구하고 꾸준히 스코어보드 맨 위쪽에서 존재하는 실력을 보인다. 서강대의 두터운 PS 실력자층을 보여 주는 확실한 지표 중 하나이지 않을까?

3등 팀 탈PS는지능순 (dreami63, nflight11)은 우리 팀이다. 더 이상의 설명이 필요할까?

4등 팀 3인분같은2인분 (coconut99, now_cow, wlgh7407)도 팀 이름에서 알 수 있듯이 실질적인 2인팀이었다. Make Yonsei Great Again(Serendipity__, JYJin, coconut99)에서 한 축을 담당하는 강호에, 내 저번 ICPC 팀을 책임진 초고수, 그리고 '요즘 폼이 심상치 않은'에서 요즘이 거의 6개월쯤 되는 것 같은 신흥 강자 wlgh7407이 모였다. 이 중 now_cow는 해외에 있어서 코딩에는 참여하지 않은 채 문제를 읽고 오더만 내렸다고 한다. 그런데도 이 정도의 순위로 대회를 마친 것을 보면 그냥 엄청나다.

5등 팀 ALL_TIME_LEGEND와 6등 팀 goraani never stop은 서강대의 강팀이다. 듣기로는 5등 팀도 오렌지가 세 명인 팀이라던데 이런 팀과 승부가 성립된 것, 심지어 3대 2로 승부가 성립했던 것 자체가 엄청 고무적인 결과다. 요즘 솔직히 의욕이 식고 11월의 ICPC 이후로는 손을 뗄 수도 있을 것 같다고 생각했는데, 그게 이번의 수상을 기점으로 완벽하게 바뀐 것 같다. 이래놓고 은퇴는 무슨 은퇴. 계속 할 거다.

 

스코어보드 공개 때 3등과 4등 팀이 2인 팀인 걸 언급해 주지 않았다고 전 회장님 Serendipity__가 굉장히 아쉬워했다. 나도 아쉽다. 언급이 확실히 됐으면 좋았을 텐데. 상위권을 공개할 때 캐스터 역할을 맡은 전전전 회장님 kukul의 텐션이 올라 가 있어서 공개가 되고 있을 때는 그런 생각도 안 들었다. 상위권 팀에 누가 있는지 다 꿰고 있더라. 역시 신촌 연합의 마스코트...! (아님)

 

With Spoiler

Live scoreboard

우리 팀 《탈PS는지능순》 팀은 총 13문제 중 A, B, C, D, E, I, J, K, L, M으로 10문제를 풀었다. 1등과 2등이 모두 H 말고 모든 문제를 풀어서 하나를 더 풀어냈다 하더라도 상의 이름이 바뀔 일은 없었겠지만, 그럼에도 아쉬운 건 아쉽다. 10솔과 11솔은 분명히 뭔가 다르다. 시간만 조금 더 있었으면 G까지는 잡을 수 있었을 텐데...

제출 기록을 살펴보고 있는데 내가 파이썬을, dreami63은 C++을 썼기 때문에 누가 이 코드 작성했는지는 한 눈에 보기 편해서 좋다. 대신 쓰던 코드를 다른 사람에게 이어넘겨 준다는 것이 어려웠다는 페널티가 있지만. 적어도 이번 SUAPC에서는 그 점이 전혀 드러나지 않았다. 팀 연습도 안 했는데 합이 이렇게 좋은 게 가능함?

그 10문제 중에서는 내가 A, B, C, E를 풀었고 나머지는 dreami63이 제출했다. 실력 차가 상당했기 때문에 dreami63이 원맨쇼를 하고 나는 한 개 혹은 두 개만 풀고 말 줄 알았는데 이 정도면 1인분은 확실히 넘었고, 혼자서 참가했더라도 수상권에는 근접할 수 있었다(!!). 팀 대회에서 이번만큼 확실한 기여를 한 적은 없었던 것 같다. 지난 ICPC는 인터넷 예선에서 쉬운 문제만 골라담았고, 리저널에서는 거의 아무 것도 못 했기 때문에 더더욱 값진 1인분이었다.

대회 타임라인은 다음과 같다. 시작할 때 나는 앞에서부터, dreami63은 뒤에서부터 보기로 했다.

 

0:03 A AC (+)

ABCDE 다섯 문제 띄워 놓고 하나씩 보다가 가장 쉬운 것 같아서 상의 없이 잡아냈다. 컨셉이 확실히 좋은 문제. 이 문제가 있어서 SUAPC 참가한 팀 중 하나도 못 맞히고 빈 손으로 돌아가는 팀은 없었다. 그 다음으로 쉬운 문제 I가 초심자와는 친하지 않은 영역인 기하 케이스워크 문제였다는 것을 감안하면 하나도 못 맞히고 불쾌한 경험 하에 돌아가는 팀이 없어서 다행이다 싶었다.

문자열을 char 단위로 수정할 수 있는 C++로 제출할까 했지만 익숙한 언어로 짜는 게 맞아서 그냥 파이썬으로 냈다. 이 정도 문제에서 틀리면 안 되는 상황이었고, 예상대로 문제 없이 맞았다.

0:22 C WA (-1)

그리디하게 남은 숫자를 지워서 마지막에 \(0 N\) 혹은 \(1 N\)만 남기는 문제. 분명히 맞아야 하는 것 같은 풀이를 냈는데 틀렸다. 혹시 몰라서 내기 전에 수 회 손으로 검증하는 과정을 거쳤는데도 이런다. 그냥 엎고 처음부터 다시 짜기 시작했다.

0:23 I WA (-1)

0:30 I AC (+1)

dreami63이 케이스워크 빡센 문제라며 잠시 열받아하다가 금방 맞아 왔다. 나는 문제를 저 시점에 안 봐서 무슨 문제인지 몰랐다. 직각삼각형 트랙을 느린 차와 빠른 차가 달리는 문제였던 것 같다. What the... 나라면 시간을 두 배는 더 썼을 거다.

0:42 C AC (+1)

100% 맞아 보이는 코드를 엎고 처음부터 다시 짰는데 그 코드가 틀릴 것 같아서 확실하게 검증하느라 오래 걸렸다. 이 정도 관찰은 실버 정도 될 것 같았는데 처음에 코드 만든 것도, 엎고 다시 짠 것도 20분씩 걸렸다는 사실은 좀 마음에 안 들었다. 수학으로 증명까지 해 놨는데 왜 이러지... 어쨌든 맞혔으나 내 마음 속에는 근거 없는 불안감이 이 때 생겼다.

0:58 D WA (-1)

1:04 D WA (-2)

1:07 D WA (-3)

이거해줘 그 1. 문제를 딱 보자마자 유니온 파인드 비스무리한 무언가처럼 풀면 될 것 같다는 생각을 했다. 다른 연결 요소라면 무조건 답이 0이고 간선이 2000개밖에 안 되니 그렇게 하는 게 맞을 것 같은데 난 구현할 자신이 없었다. 풀이를 열심히 생각해 냈는데, dreami63이 금새 개선했다. 같은 연결요소라도 길을 따라가지 않고 축지법 두 번을 쓰는 경우가 가능했다. 그래서 dreami63에게 밑고 맡겼다. 두어번 틀리더라도 푼 문제 수로 밀어버리면 되니까.

dreami63이 D를 푸는 동안 나는 수학 냄새가 빡 나는 E를 풀러 갔다.

1:12 E WA (-1)

그리고 틀렸다. 멍청하게 필요도 없는 PQ를 돌리고 있었다. 문제의 조건을 만족하는 수열의 가장 큰 항 갯수가 20만도 안 된다는 것을 증명해낸 다음 그냥 내장된 정렬 함수를 쓸 수 있도록 코드를 개선해 나가고 있었다.

1:13 D AC (+3)

머리 싸매고 있는 동안 dreami63이 멋지게 슥삭 해치우고 많이 풀린 L을 잡으러 갔다.

1:33 E AC (+1) : First Solve!

나도 금방 낸 구멍을 복구해서 돌아왔다. 체크하는 동안 수열의 1번부터 N번 항을 검사하는 대신 1부터 N을 검사해버리는 머저리같은 실수 때문에 시간을 좀 날려먹었다. 왜 그랬을까... 그런데 그러고도 퍼솔이었다. 으잉??

3의 배수나 5의 배수가 아닌 것들은 모조리 집어넣는다. 이 시점에서 \(N < 200\,000\)인 것만 집어넣어도 10만개는 넘어가기 때문에, 20만보다 작은 수만 집어넣어도 10만개의 항은 모조리 집어넣을 수 있다. 3의 배수이거나 5의 배수인 것은 반드시 \(3^{i+3j}5^{i+3k}x\)이다. 물론 \((x,15)=1\)이다. 다 집어넣고 정렬 돌리면 10만개의 항을 \(\mathcal{O}(N)\)에 전처리 할 수 있다.

말리기 쉬운 문제라 잘못된 풀이 들고 이걸 잡고 있었다가는 10번씩 틀리는 것도 이상하지 않은 문제기는 했다. 한 번만 틀리고 맞힌 내가 운이 좋았다고 생각하기로 했다. 실제로 3인분같은2인분과 우리 팀 말고는 다 세 번씩은 틀리고 맞혔으며, 12번을 시도하다가 장렬히 산화한 팀도 있었기 때문에. 하지만 이 시점까지 푼 팀 자체가 없다는 건 좀 의아했다. PS:Endgame이나 Redshift는 충분히 가능했을 텐데... 다른 문제를 풀다가 늦었나?

이 시점에서 근거 없는 불안감이 완전히 날아갔다. 하나 정도는 반드시 내가 잡을 수 있다는 근거 희박한 자신감만 충만해졌고, 그나마 남은 문제 중 수학 맛이 좀 나는 B를 잡으러 갔다. 풀이 비스무리한 게 보였기 때문에...

1:39 L AC (+)

한 번에 맞아 왔다. 인터랙티브 문제라서 쉽지 않을 것 같은데 이걸 쉽게 해내는 dreami63은 신인가??

1:55 B AC (+)

처음에는 \(a_i \leftarrow \frac{a_i + a_{i+1}}{2}\)을 100번쯤 하면 항상 평균으로 수렴하겠지? 싶어서 그런 풀이를 짰다. C랑 E에서 한 번씩 틀려 오면서 이번에는 신중을 기해야지 해놓고 랜덤으로 뽑은 테케를 돌렸는데 평균은 무슨, 100번을 돌려도 편차가 0.5% 정도는 생겼다. 저걸 어떻게 하면 처리할 수 있을까 했는데 갑자기 내 머릿속을 스쳐가는 랜덤 풀이.

작년 ICPC 대비 팀연습에서 랜덤으로 한 문제를 먹은 기억이 나서 매번 섞어 주고 인접한 수의 평균을 저장하는 기법을 써 봤다. 랜덤 인풋 한 열 번 돌려봤는데 소수점 첫째 자리까지 맞아떨어져서 이건 100% 정답이다 하고 냈고, 한 방에 맞았다. 이 시점에 도파민이 폭발한 것 같다.

출제자나 검수자들은 랜덤 풀이의 존재성 정도는 당연히 알았을 것 같지만, 이 문제 푼 사람 중에서 랜덤으로 뚫은 사람이 있을지는 잘 모르겠다. 일단 내가 기여하면 무조건 무작위화 태그는 넣을 거다.

2:32 M AC (+)

이거해줘 그2. 푼 문제 수가 남은 문제 수보다 많아지면서 절대 안 풀릴 것 같은 문제 F와 H를 거르고 나머지를 보고 있었다. M의 제한을 잘 보니 충분히 물 주는 횟수 \(X\)가 커질 때 주기적으로 돌아가는 꼴이었고, 세그먼트 트리랑 같이 돌리면 풀릴 것 같다는 판단을 했다. 마침 다음 문제 탐색 중이던 dreami63에게 풀이를 열심히 설명했고, 나 이거 구현 못함 님이 해줘 이 소리를 두 번이나 해 버렸다. ㅋㅋ.

풀이 듣고 조금 있다가 바로 AC를 따 왔다. 진짜 dreami63은 신인가?? (2)

스트리밍에서 듣자 하니 이 문제에 세그먼트 트리 대신에 상수가 큰 pbds를 사용했다가 폭사한 팀이 적지 않게 있었다고 한다. 아이고 저런... 

2:41 H TLE (-1)

그런데 왜 H를 도전했냐고? 사실 저기에 들어간 건 H의 풀이가 아니다. J의 풀이지. dreami63이 J를 잡고 있다가 시간 제한이 같은 H번 문제를 TLE 판별기로 사용했다. 스코어보드 보니까 어차피 풀이 듣기 전까지는 못 풀 것 같다는 확신이 강하게 들었기 때문에 그랬던 것 같다. 왜 같다냐면 나는 그 때 K를 잡고 있었기 때문이다. 중요한 관찰 하나를 해 버려서 한시라도 빠르게 풀어내어 더 위로 올라가고 싶었다.

2:42 K WA (-1)

그리고 틀렸다. 이런 미친... 분명히 수학적으로 맞고 틀리면 안 되는 풀이 같은데 틀려서 코드를 살짝살짝 수정해 보고 손으로 적당한 예제 하나 그려넣어서 돌려 봐도 정답만 나왔다. 그렇게까지 어려운 문제가 아닌데 왜 틀리지? 싶어서 머리만 싸맸다.

2:43 H TLE (-2)

2:49 H TLE (-3)

2:51 H TLE (-4)

그러는 동안 dreami63은 bitset 풀이를 더 빠르게 돌리기 위해서 H에 TLE를 쌓고 있었고... 그러는 동안 대회 시작 후 3시간이 경과해서 스코어보드가 얼었다.

3:00 J AC (+)

그리고 21초 후에 dreami63이 J를 맞혔다. Bitset이 정해가 아닐 것 같다고 말하고 있었는데, 스트리밍에서 까 보니 bitset 문제였다. "Bitset... 알아야겠지?" - kukul

나는 아직까지도 분명히 맞는 것 같긴 한데 확실히 틀리는 K 코드를 보고 씨름하고 있었다.

3:25 K AC (+1)

결락의 원인은 root와 v가 같을 때 처리를 안 해 주는 것이었다. 지금 다시 로컬에서 테스트 해 보기 전까지도 파이썬의 정수 오차가 문제인 줄 알았는데, 그게 아니라 LCA를 통해서 케이스를 나눠 주는 것에서 실수가 있었고 그 탓에 root와 v가 같은 경우 이상한 답을 내는 것이었다. 지금도 그 한 줄만 고치면 잘 돌아갈 것 같다. 이건 나중에 Open Contest 끝나고 문제 올라오면 돌려 봐야겠다.

하여튼 그 때는 나나 dreami63이나 기상천외하게 돌아가는 코드의 문제점이 파이썬의 정수 오차인 줄로만 알아서 dreami63이 코드를 가겨가서 C++로 포팅했고, 금세 맞히고 돌아왔다. 쩝. 한 줄만 고쳤으면 괜히 귀찮게 안 만드는 거였는데...

 

이 이후로는 보스급 문제들만 남았다. F나 H는 운영진 예상이 다이아몬드인 초고난도 문제였고, 그 중 H는 맞힌 팀이 단 하나도 없었다. 어쨌든 남은 시간이 90분은 넘었으니 세 개 중 하나만 잡으면 3등은 확정인 분위기였다.

F는 dp로 그래프를 만든다는 것까지는 너무 당연하지만 그 다음으로 어떻게 나아가야 할지는 생각이 안 났다. 걸렀다.

H는 persistent segment tree 아니면 각 permutation을 보관하고 lazy하게 갱신해 주는 segment tree 정도가 생각났다. 이것도 그런데 답을 어떻게 얻어야 할지 전혀 생각이 안 났다. 걸렀다.

유일하게 남은 것이 G였고, ETT 수열을 괄호 문자열로 보며 그 때 올바른 괄호 문자열의 갯수를 알아내는 방법까지는 대충 알아냈다. 유사한 문제 역시 발굴해 냈고, 그 문제의 풀이가 쓰여 있는 블로그에서 결정적인 힌트를 얻어서 \(\mathcal{O}(N^3)\)짜리 DP를 구현하기 시작했다. 그러나 F와 H에 대한 아이디어를 부분적으로 내고 거를지 말지 결정하는 동안 시간이 너무 흘렀다. 끝나기 1분 전까지 코드를 완성해 내지 못했고, 이 문제를 맞히는 건 오픈콘 종료 후까지 미룰 수밖에 없었다. 아니 근데 저 유사한, 정확하게는 하위호환 문제가 플3이던데??? 답의 90% 정도 완성해 낸 것도 잘 한 것이라고 생각하자.

 

대회 끝나자마자 동방에서 같이 대회 치른 PS:Endgame과 같이 치킨 먹으면서 복기했다. 2인팀이니까 ×1.5 보너스 안 주냐는 실없는 말도 했고. 근데 kiwiyou까지 있었으면 G를 풀어서 11솔은 금방 했을 것 같긴 했다는 점에서 좀 아쉽다 ㅋㅋ. 12솔은 사실 잘 모르겠다. F 저거 다이아 mcmf 문제던데 대회 중에 풀릴 수가 있나? 일단 나는 flow를 거의 하나도 몰라서 대회 중에 아이디어를 낼 확률은 없다. 그렇다면 나머지 둘에게 전적으로 맡겨야 하는데...

H는... 저건 그냥 풀지 말라는 문제인 것 같은데? 스플레이랑 링컷이라니 무슨 괴물같은 문제를 낸 건가 hjroh0315... 어떻게 세팅했는가가 사실 더 궁금하다.

 

이 멤버로 아마 ICPC도 나갈 텐데, 마지막을 이번처럼 화려하게 장식할 수 있었으면 좋겠다. 지난번 리저널을 보니 다이아 밭이던데 그게 가능할지는 모르겠지만, 그래도 이번 대회에서 예상 난이도 플래티넘도 풀어내면서 1인분을 넘게 할 수 있었던 것은 지금까지 PS를 그래도 완전히 유기하지는 않고 지속했기 때문이라고 생각한다. 그리고 8대 플래티넘을 위해서 이것저것 풀면서 수학 원툴에서 수학 빼고 다른 것도 어느 정도 할 수 있는 레벨까지 올라왔기 때문이고.

아직 멈추기는 조금 먼 것 같다. 계속 달려야지. 느리더라도.