SUAPC 2021 winter 후기

좀 늦은 후기이지만 최대한 생생하게 후기를 써봐야 겠다. 

 

우선 대회는 dicohy27, hwon233과 민초의 난이라는 팀으로 나가게 되었다.

코드포스 레이팅이 민트가 다 민트라서 민초의 난이라는 팀으로 네이밍을 하였는데 나는 pupil인건 비밀  

 

사실 워낙 잘하는 두 친구고, 뭔가 이렇게 ps를 좋아하는 사람과 팀을 하는 것은 처음이었다. 

 

우리는 먼저 내가 0, hwon233이 1, dicohy27이 2를 맡아서 문제를 보고, 이후 스코어보드 솔브되는  문제들을 풀기로 하였다. 

 

철저하게 내 시점으로 얘기를 해보겠다. 

 

A

lky님이 냈다는 생각, 독특한 계산기와 같다는 생각, 그리고 이건 오프라인 쿼리? 같은 형식으로 돌아갈 것 같다는 생각을 하고 바로 패스를 하고 D로 넘어갔다. 

 

 

D 문제를 읽는 도중에 아마도 스코어 보드에 첫 솔브문제가 출현을 하여서 dicohy27이 I를, hwon233이 보고 있던 B를 계속 보기로 하였다. 

 

I를 풀었다는 소식을 듣고, 나는 문제를 D,E 순서대로 보기 시작했다. 

 

그렇게 B가 계속해서 풀린다는 스코어 보드를 확인하고 나도 B를 보았고, LIS의 갯수를 계속해서 반복하는 N^2의 알고리즘이 필요하다는 것을 알았다. 

 

근데 조금 생각을 해보니 무조건 O(N)의 풀이가 가능할 것 같았고, 내가 풀 수 있다는 확신이 들어서 B를 맡겠다고 한게 아마 이번 대회의 가장 큰 패착이 아니었나 싶다. 

 

B를 푸는데 처음에는 배열도 필요없이 최대 최소만 관리하는 형식으로 짜면 될 것같아서 짜고 나서, 제출하기전에 반례를 떠올리고 다시 덮고, set에 lower,upper bound를 사용해서 풀면 어떨까 생각을 하였다. 

 

내가 생각하기에 반례도 없었고, 하지만 왠지 모를 불안감과 제출을 한 결과 1WA, 바로 dicohy27이 중복 불가에 대한 반례를 찾아 주었고, 처음 들어보는 multiset이라는 자료구조를 사용하였지만 2WA 아마 30분 경과때 이걸 제출했던 것 같은데...

 

이걸 2시간 30분이 경과할때까지 반례를 찾았다. 사실 이때 엄청나게 많은 좌절을 느꼈다. 스코어 보드 상 B를 푼팀은 엄청나게 많았고, 나는 그 전 연습에서 독서실 거리두기나, 실버런에서 끝까지 반례를 못 찾았기 때문에 이번에도 반례를 못 찾는 병신이라고 생각을 하였다. 

 

그러다가 hwon233이 문제를 다시 같이 보았고, 다시 읽은 결과 -> 이렇게 떡국 그릇을 쌓는게 아니라, 순서에 상관없이 떡국 그릇을 쌓을 수 있는 것이었다. 그래서 바로 hwon233이 제출을 하고, AC.

 

이때는 5솔을 한 시점이었고, C로 넘어갔다.

 

C는 dicohy27과 같이 보았는데 dp인것 같다는 생각을 하였고, 같이 풀이를 떠올렸다. 

내 풀이와 달랐는데, 확신이 찬 것 같아서 dicohy27에게 맡겼는데 한 20,30분만에 뚝딱하더니 AC 

 

1시간 정도 남은 그 와중에 hwon233은 F를, 나는 J를 보았다. 

 

J는 먼저 N^3의 풀이, 그리고 seg를 이용한 N^2logN이 떠올랐다. 도저히 N^2이하로는 줄일 수가 없을 것같아서 뭔가 내가 모르는 알고리즘이 필요하지 않을까라는 생각에 끝까지 규칙이 뭔지 찾을 생각은 하지 않았던 것 같다. 

 

그렇게 그대로 6솔로 마무리를 하였다. 

 

다들 엄청나게 아쉬워 했고, 뭔가 1인분은 커녕 0.5인분도 못했다는 사실에 분했다. 

 

일단 계속해서 팀으로 대회를 참가할 것 같은데 폐가 안되게 정말 열심히 해야겠다. 그리고 코드포스도 좀 진지하게 참가해야겠다. 

 

그리고 두명은 분했는지 곧 바로 블루를 찍었다. ㅋㅋㅋㅋㅋ 

 

아 그리고 업솔빙을 하면서 느낀건데 난 진짜 무슨 머저리 같다 map을 이번에 처음 사용하였다.

공부 좀 열심히 하자 맨날 입맛대로 하지말고