2022 ICPC Seoul Regional 후기

10위를 했다

일단 이번 리저널은 별 기대를 하지 않은 채 참가했다.
그 이유는
1. 리저널 일주일 전에 월파를 조져서 자신감이 똑떨했다
2. 일주일 전에 내가 코로나에 걸려 컨디션이 안 좋았다. 다행히 대회 당일에 격리가 풀렸다.
3. 팀원 한 명이 코로나에 걸려 대회에 2인으로 참가해야했다. 이 때문에 월파진출에 대한 기대는 사실상 접었었다.

그래서 나는 이 대회를 마지막으로 PS를 접을 생각이었기 때문에 그냥 "수상권만 들고 유종의미만 거두자!"라는 생각이었는데 괜찮은 결과를 얻은 것 같다. 3년만의 오프라인 서울리저널이라 재미도 있었다 ㅎㅎ

팀원은 다음과 같다.
knon0501: SCPC 2022 4등상, ICPC 2020 7등
Amel: SCPC 2021 4등상, ICPC 2021 13등
팀연습을 여러번 해봤는데 서로의 강점이 달라 시너지가 잘 나는 조합인 것 같다.

~0min

전날 이슈가 있어서 잠을 3시간 밖에 못 자서 컨디션이 매우 안 좋았다. 나는 8시 50분에 도착하고 태훈이는 9시 5분에 도착해서 아슬아슬하게 등록을 했다. 똥마려운데 대회 전에 못싸서 5시간동안 똥을 참아야했다...

0min

내가 문제지를 뜯어서 읽고 태훈이가 로그인하고 VScode 세팅을 대충했다.

8min

슼보에서 J가 풀려서 태훈이가 읽고 짜서 맞았다.

17min

태훈이가 I를 설명해줘서 내가 LCS를 짰다. 약간의 코딩실수가 있었지만 바로 맞았다.

40min

K는 지문이 길고 쓸데없는 말이 많은데 결국 세 문자열의 LCS 비슷한 걸 구하는 문제이다. 메모리 제한이 어디 적혀있는지 모르겠어서 바로 코딩을 들어가진 않았는데 2GB라는 것을 알고 F를 짜던 태훈이를 비키게 하고 짜서 맞았다.

47min

내가 코딩을 하는 사이 태훈이가 F의 디테일을 완성하고 바로 코딩해서 맞았다.

83min

내가 다익스트라 응용인 E를 잡았다. 코딩에서 좀 버벅여서 밀고 다시짜고 실수가 좀 있어서 2번 틀리고 맞았다.

104min

태훈이가 D에서 끙끙대고 있길래 내가 본 다음 DP식을 완성하고 다이나믹 세그를 이용하면 된다고 했다. 그랬더니 태훈이가 굳이 다이나믹을 쓸 필요는 없다며 뚝딱 짜고 맞았다.
이 때까진 분위기가 괜찮았다. 2명 치고 괜찮은 속도였고 중간에 무려 5등까지 올라가기도 했다.

197min

C는 작년 인터넷 예선의 응용이었다. 나는 작년 예선을 나가진 않았지만 문제를 사골까지 우리는 한국 리저널의 특성을 알고 있었기 때문에 최근 기출을 공부해서 삼각형 버전의 풀이를 알고 있었다.
결국 볼록과 오목을 잘 세면 되는 건데 오목사각형이 잘 안 세졌다. 태훈이가 반례를 제시해서 알고리즘이 틀렸다는 걸 깨닫고 각도 정렬을 하고 스위핑을 하는 $O(N^3 \log N)$풀이를 만들었다. 나는 코딩을 하기 싫어서 태훈이가 코딩을 했는데 예제가 안 나와서 한참동안 디버깅을 하다가 오타 하나를 발견해서 수정하고 맞았다.
C를 풀고 얼마 뒤 슼보가 프리즈되었다. 우리는 남은 시간동안 A와 L을 풀자는 계획을 세웠다.

281min

L은 2n-3이라는 숫자가 수상해 보여서 dfs트리를 만드는 방법으로 접근을 했더니 일자그래프인 경우 길이 3인 사이클이 무조건 존재하고 아닌 경우 비둘기집 원리에 의해 길이가 같은 백엣지가 무조건 존재한다는 사실을 알 수 있었다. 그리고 태훈이가 코딩을 후딱하고 제출했는데 틀렸다... 나도 코드를 같이 봤는데 틀린점을 도무지 모르겠어서 dm을 짜보기도 하고 내가 처음부터 코딩을 해보기도 했는데 계속 TLE나 RTE를 받았다. 결국 30분쯤을 남기고 assert디버깅을 해서 우리가 dfs를 잘못 짰다는 사실을 깨닫고 눈물을 흘리며 고쳐서 맞았다. 그래도 맞은 게 어디야... 하하

~300min

남은 시간 동안 A를 봤는데 분명 그런디 같지만 어떻게 풀 지는 잘 모르겠었다.

300min~

나는 대충 수상권 안에는 들 것 같다고 생각했고 태훈이는 수상권에도 못 들 것 같다고 했는데 생각보다 높은 등수인 10등을 기록했다.
L에서 뻘짓을 안 했으면 9등은 했을 것 같고 3인팀이었으면 A도 풀었을 것 같다는 생각이 들지만 어짜피 숭실대가 너무 쎄서 월파 못 가는 건 매한가지다. 그래도 이 정도면 나름 유종의 미 거두고 PS 은퇴하는 것 같다. 후기끝!