solved.ac Grand Arena Party (Arena #18) 후기

solved.ac에서 주최한 Grand Arena Party (Arena #18) 에 Division 1으로 참가하여 1등을 달성하였다!

SCPC, SNUPC(교내대회), Hello BOJ 등등 개인 대회에 나간 적도 많고, 상도 많이 타긴 했지만 우승은 한 번도 해 본 적 없었는데, 이번에 정말 운이 잘 따라줘서 우승을 하게 된 것 같아서 좋았다. 바로 3주 전에 Hello BOJ 2024 대회 출제 및 당일 운영을 하면서 정말 힘들었었는데, 여기 나와서 1등도 하고 상품도 타가니 앞으로는 참가할 수 있는 대회면 참가를 해야겠다는 생각이 드는 하루였다.

대회 시작 전

적당히 11시 언저리에 도착해서 들어오니 다들 열심히 Puzzle hunt를 하고 계시던데, 우리 팀은 팀원을 한 분 (kiwiyou님) 빼고 찾을 수가 없어서 한 12시까진 그냥 멍때렸던 것 같다. 근데 사람들이 다들 앉으니까 근처에 팀원들이 많이 있었어서 12시부터 40분동안 열심히 풀었다. 좀 더 일찍 시작했으면 퍼즐 더 많이 풀었을 듯 한데 아쉬웠다. 생각했던 것보다 많이 재미있었어서 아예 정규 일정으로 시간을 잡아두는 것도 좋아 보였다.

대회장 앞에 풍선이 잔뜩 묶여 있었는데, Hello BOJ 때랑 같은 업체에서 시켰는지 몰라도 그 때랑 똑같이 풍선 다발이 풍선으로(..) 묶여 고정되어 있었다. 그땐 업체에서 색깔도 다 섞어서 줘서 분류하느라 고생이었는데 그래서 그런지 이번에는 색깔별로 잘 묶여 있었다. 어쨌든 하나씩 나누려면 묶인 풍선을 먼저 잘라야 하는데, shift님이 가위를 들고 뭔가 고전을 하시는 것 같길래 내가 슥 가서 가위 뺏어들고 다 잘라드렸다. 이 때 선행 스택 쌓아서 보상을 받았나 보다.

대회 시작 직전까지는 별 생각이 없었고, 다만 대회 장소가 방열이 잘 안 돼서 그런지 좀 추웠다. 하지만 추워서 각성 상태가 잘 유지되는 것 같길래 그냥 대회를 치기로 했다.

대회 타임라인

대회 문제가 난이도순이 아니라고 들었던 것 같은데 찾아보기 귀찮아서 그냥 가만히 있었다. 시작하자마자 일단 A번은 쉽겠거니 하고 읽었는데 다행히 쉬운 게 맞아서 적당히 금방 풀었다. (2분 AC)

그리고 B를 봤는데, 딱 봐도 누가 5분컷 낼 거 같이 생겼는데 너무 어려워서 망했나? 하는 생각이 일단 들었다. 그래서 C를 열었는데 무슨 볼록다각형을 주길래 D로 넘어갔고, D는 어디서 많이 본 주유소 그리디 문제처럼 생겼었다. E~H까지 열어서 다 읽으려다가 그러면 시간 너무 많이 쓸 것 같아서 적당히 멈추기로 했고, D가 분명 비슷한 문제를 예전에 풀어본 적이 있어서 대충 비슷하게 하면 되겠거니 하고 생각을 좀 해 보았다.

D처럼 생긴 문제는 연료 탱크에 "예비 연료"를 싼 것부터 최대한 채우고 실제로 운행할 때 꺼내 쓰면서 그 때 비용을 지불하는 식으로 풀면 보통 잘 풀 수 있는데, 얘도 그렇게 풀 수 있을 것 같고 일단 적당한 시간 내에 짤 수 있을 듯 해서 D를 먼저 짜기로 했다. 대충 이때까지도 B를 아무도 못 풀었길래 나만 망한 건 아닌듯 해서 안심이 되었다. D를 열심히 짜고 내니까 다행히도 한 번에 맞았다. (20분 AC) 이때까지도 2솔이 한 4명 있었나 그랬던 것 같다.

그리고 나서 이젠 진짜 B를 풀어야겠어서 생각을 천천히 해 보았고, 역시 다른 문제를 보고 넘어오니까 이번에는 그럴듯한 생각이 났다. 일단답에 대한 이분탐색은 해야겠고, 결정 문제를 푸는 좋은 그리디가 생각이 안 났던 거였는데 D 값이 낮은 전자기기부터 플러그를 배정한 뒤 남은 플러그는 멀티탭을 구멍 많은 것부터 싹 꽂아서 다음 레벨로 밀어버리는 식의 그리디를 떠올릴 수 있었다. 틀리면 어쩌지 하면서 짜고 냈는데 맞아서 다행이었다. (28분 AC)

그리고 나서 C도 다시 읽고 뒤쪽 문제도 일단 다 읽었는데, 그 사이에 누가 E를 풀었길래 나도 E를 좀 봤다. 뭔가 먼지가 없을 때 간 경로를 union-find로 관리해야겠다는 생각까진 할 수 있었는데 이동 횟수를 구해야 해서 그것 때문에 구현이 좀 헷갈렸다. 거기에 더해서, (행, 열, 방향)의 변수 3개를 관리해야 해서 그냥 그거 때문에 머릿속에서 그림이 잘 안 그려져서 더 헷갈렸던 것 같다. 어찌어찌 예제가 나오게 하는데는 성공을 해서 일단 내 봤는데, 틀렸다. 문제 특성상 디버깅용 예제를 만들기가 정말 힘들어서 그냥 코드를 한 번 더 살펴 봤는데, 다행히도 식 잘못 쓴 부분을 금방 발견해서 고쳤더니 맞았다 (72분 AC). 이때쯤 다들 B, D, E 중 하나에서 고전하고 있었어서 그런지 상당히 오래 나만 4솔인 상태였던 것 같다.

뒤쪽 문제는 그냥 감을 잡는 데 시간이 너무 오래 걸릴 것 같았고, C가 왠지 금방 풀릴 수도 있을 것 같아서 좀 보기로 했다. 둘레 절반을 기준으로 분할하는 것은 쉬우니 그것을 바탕으로 생각을 하면, 둘레 절반 분할 선을 반 바퀴 돌리면 그 사이에 반드시 답이 있다는 사실을 알 수가 있어서 그걸 찾는 걸 구현하면 풀리는 듯 했다. 구현은 다각형 변 내분점 구하고 넓이 구하기 + 이분탐색 끼얹으면 끝이라서 생각보다 금방 했는데, 이게 실수오차가 어떻게 날지를 전혀 예측을 할 수 없어서 일단 예제 나오는 코드를 냈더니 틀렸다. 그럼 그렇지 하면서 다 long double로 때려넣고 + 답과 충분히 가까운 걸 찾으면 즉시 종료하도록 수정해서 냈더니 다행히 맞았다. (101분 AC). 출제진 중에 이런 문제 냈을 거 같은 사람이 딱 한 명 있었는데, 정확히 그 사람이 퍼솔 풍선을 들고 왔다..

그리고 나머지 세 문제를 보니까 H가 좀 풀렸길래 그럼 나도 풀어야지 하고 H로 넘어갔다. H는 나름? 전형적인 "트리 순회해서 번호붙이고 구간으로 만들어서 자료구조쓰기" 문제였고, 역시 풀이는 적당한 시간 내에 나왔다. 구현할 시간도 한 시간 언저리 있길래 "아 6솔하고 우승하면 되겠다~" 라고 속으로 생각하면서 코딩을 시작했는데.. 그게 플래그였나 보다. 예제 나오게 하는 데 거의 30분 정도 디버깅에 쏟고, 제출하니까 틀리길래 왜 틀리지 하고 코드만 뚫어져라 보다가 시간이 끝났다.

대회 후

6솔한 사람이 있을까봐 잠시 걱정했는데, 정황상 없는 듯 해서 그냥 안심하고 남은 일정동안은 발표 듣기 + H 왜 틀렸는지 찾기에 시간을 보냈다. 그리고 나서 스코어보드 공개 + 시상식이 있었고, 역시 6솔이 없어서 내가 1등이었다.

Div2 대상이 kiwiyou님이셨는데, 퍼즐 헌트 같은 조였다 ㅋㅋ 이런 우연이..

소감

문제들이 난이도와 별개로 코딩하다가 멸망하기가 매우 쉬워서 잘하는 분들이 다들 한 번씩 걸려 넘어지신 듯 한데, 나는 초반에 한 번도 안 넘어지고 5문제를 빨리 풀어서 그것을 바탕으로 우승할 수 있었던 듯 하다. D를 다들 어려워하던데 나는 비슷한 걸 풀어봤어서 금방 풀고 넘어간 것도 좋았고, 특히 C가 좀 풀기 싫게 생겨서 다들 안 잡은 듯 한데 내가 어떻게 빨리 풀고 넘겨버린 것도 유효했던 것 같다.

사실 요즘 들어 회사일 하면서 시간 내서 PS 하는 것도 피곤하고, 그냥 어려운 문제 풀려면 머리 아픈데 회사일 말고 머리아플 일을 또 만들어야 하나 싶어서 PS 흥미가 좀 떨어졌었다. 근데 오늘 대회 우승한 덕분에 월파 전까지는 그래도 PS 열심히 할 수 있을 듯 하다.

앞에 나가서도 잠깐 말했었지만 H번을 시간 엄청 남겨두고 못 푼게 굉장히 아쉬운 부분이었는데, 집 가서도 한참을 더 디버깅하다가 틀린 이유를 찾아버렸다.

lazy 뿌려줄 때 저 두 줄을 안 적었다;; lazy 하루이틀 짜는것도 아니고 뭐 저런 실수를 하나 싶은데, 3시간 대회도 이제는 너무 힘든 체력이 되어버린 걸까..