[대회] 2021 Sogang Programming Contest (Master) 후기

지난 27일 교내 프로그래밍 대회 (SPC)가 열렸다. 입학한 뒤로 학교에 갈 일이 별로 없었는데, 대회가 대면으로 진행되어서 좋았다. 학교에서 많은 사람들을 한 번에 만난 적이 없었어서 대면인 것 자체로 재미있었던 것 같다 ㅋㅋ slack에서만 보던 사람들을 되게 많이 봐서 신기했다ㅋㅋ


처음으로 뭔가 욕심내서 준비한 대회였다. 혹시 몰라서 자주 하는 실수들과 내가 아는 알고리즘 코드들을 대회 노트로 만들어서 갔다.
내 목표는 6등(동상 수상컷)이내에 드는 것이었는데, 아쉽게도 4솔 9등으로 마무리했다. ㅠㅠ

스코어보드

타임라인

삽질한 게 너무 잘 기억나서 최대한 자세히 썼다! ㅎㅎ;

A. Ресторан

대회가 시작하고 문제를 읽자마자 바로 구현에 들어갔다. 근데, 아스키코드 값이 기억이 안 났다. '아 노트에 아스키 코드표라도 넣어올걸'이라는 생각을 잠시 했다. 소문자 a는 97인 게 기억났는데 대문자 A의 값이 기억이 안 났다. 대충 60번대 였던 것 같아서 61부터 넣어가면서 확인해보려고 했다. 한두 번 확인하다가 그냥 -'A' + 'a'를 하면 되는구나를 깨닫고 AC를 받았다. 스코어보드를 보니 대충 한자리 등수였다. 기분이 매우 좋았다. (??: 수상하는 상상함ㅋㅋ)
(00:05 AC)

---

B. 벼락치기

나를 망하게 한 아주아주 쉬운 문제이다.
A번을 풀고 B번을 읽었다. 읽어보니 브론즈나 실버 문제겠거니 하고 신나게 구현을 했다. 제출 전 스코어보드를 보니 B를 푼 사람이 거의 없어서 기분이 좋았다 ㅋㅋ. 5초 뒤에 바로 기분이 안 좋아졌지만.
(00:15 WA)


스코어보드를 보니 다른 사람들도 WA를 많이 받았길래 안심하고 코드를 다시 보았다. 문제에 따르면 남은 시간이 절반 이상이어야 하는데 나는 절반 초과라고 생각하고 문제를 풀었던 것을 발견했다. 그래서 바로 부등식을 고쳐서 제출하였는데 WA를 받았다. 이 때부터 똥줄타기 시작했다 ㅋㅋ 분노의 삼다수 drinking을 시전했다.
(00:19 WA)


다시 스코어보드를 보니 다른 사람들이 슬슬 AC를 받고 올라가더라.. 그래서 쉬운 문제인데 뭔가 내가 놓치고 있는 거라 생각을 해서 문제를 계속 다시 읽어보았다. 그리고 내가 만든 테케를 한 5개 정도 돌려봤는데도, 다 맞더라. 이때, 멘탈이 나간 것 같다. 그래서 지금 보면 의미 없는 코드 수정을 하고 제출하였고 당연히 WA를 받았다.
(00:32 WA)


여기서 망했다 싶었다. 그래도 멘탈을 잡고 그냥 다른 거 먼저 풀자라는 생각을 했다. 당시에 C보다 D를 푼 사람이 많아서 D로 넘어갔다. D의 그림을 보자마자 '오 이거 스위핑 문제다'라는 생각을 했다. 문제를 읽고 구현을 하기 전에 다시 스코어보드를 봤는데, 잠시 사이에 사람들이 B를 정말 많이 맞췄더라. 그래서 갑자기 미련이 생겨서 B를 한 번 더 보았다. (이때 B를 다시 볼 게 아니라 그냥 C를 풀러 갔어야 했다ㅠㅠ) 역시나 별 이상한 점을 발견하지 못했고 아무 의미 없는 코드 수정을 하고 제출하였다. 또 WA.
(00:49 WA)

---

D. 버스 노선 개편하기

B때문에 멘탈이 나간 상황이었지만 다행히 읽으면서 풀이가 떠오르는 문제였다. 최근에 스위핑 문제들을 몇 개 풀었었는데, 도움이 된 것 같다. 바로 구현했고, 제출하기 전에 문제를 한 번 더 읽어보았다. 테케도 하나 만들어서 실행해보니 맞길래 제출했다. 한 번에 맞았다! 스코어보드를 보니 D번 역시 푼 사람이 거의 없어서 아직 할 만하다고 생각했다.
(01:00 AC)

---

E. Player-based Team Distribution

C번을 풀고 딱 2시간이 남아있었는데, B번으로 다시 가면 진짜 망할 것 같다는 생각을 했다. 이때, 내 기억에 1등과 2등만 E번을 해결했더라. 그래서 E로 넘어왔다. 문제를 읽어보니 점수가 음수인 플레이어는 혼자 팀을 구성하고, 점수가 양수인 플레이어들을 최대한 몰아넣으면 최대가 될 것 같았다. 쉬운 그리디구나 싶었다. (이런 촉은 보통 틀리더라) 예제가 잘 돌아갔고, 제출했다.
(01:04 WA)


코드를 다시 보니 0일때도 양수인 팀에 넣어줘야 하는데 이걸 놓쳤다. 다시 제출했다. 당연히 틀렸다. 2명밖에 못풀었던 문제기 때문에 쿨하게 넘어가자 생각해서 넘어갔다.
(01:07 WA)

---

B. 벼락치기

E를 호기롭게 덤볐다가 틀리고 스코어보드를 봤다. 대부분은 B를 맞췄더라. 이때, 20위 이내에서 내 동기 3명이랑 나만 못 풀고 있어서 좀 웃겼었다 ㅋㅋㅋㅋ. 암튼 B는 반드시 풀어야 하는 문제라 생각해서 다시 보기 시작했다. 또 의미 없는 수정을 하고 WA를 받았다.
(01:12 WA)


이때 갑자기 내가 적어온 실수노트가 생각나더라. 실수노트를 읽으니 부등식 오차 조심하라고 써있더라. 아 여기서 머리가 띵했다. 진작 좀 읽을 걸.. ㅠㅠ 부등식 r>= arr[i]/2를 2*r >= arr[i]로 바꾸고 바로 AC받았다. 이런 실수를 하다니 진짜 바본가? (맞다)
(01:17 AC)



여담으로 B번 문제에 롸선배가 나온다. B번이 너무 안 풀려서 괜히 롸선배가 얄미웠다.
E번을 포기하고 B로 넘어와서 다시 보고 있었는데, 대회 관계자가 사진을 찍으러 오더라. 얼굴을 봤는데 롸선배였다. 이때 혼자 웃겨서 웃음이 살짝 터졌는데 날 찍으려고 하길래 열심히 푸는 척하면서 웃음을 참았다 ㅋㅋㅋㅋㅋㅋㅋㅋ. 암튼 롸선배가 다녀간 뒤로 B를 맞춘 거로 기억한다. (롸의 기운?) 감사합니다. ㅎㅎㅎㅎ

photo by raararaara

---

C. 야바위 게임

C로 넘어갔다. 나는 이미 10위권 밖이었다. 1등과 2등을 제외한 사람들은 대부분 A,B,D를 해결한 상태였던 것으로 기억한다. 암튼 C번을 보았고, DFS를 통해 해결할 수 있을 것 같았다. 그런데 문제가 있었다. 이미 지나갔던 곳이어도 다른 경로를 통해 도착했을 때 답이 되는 경우가 존재하더라. 그래서 조건문을 통해서 이미 갔던 곳이더라도 거리의 홀짝이 다른 경우엔 방문하도록 하였다. 예제가 돌아가서 신나서 제출했고 틀렸다.
(01:48 WA)


다시 코드를 보니 방문처리에서 이상한 점을 발견해서 고치고 다시 냈다. 역시 틀렸다.
(01:50 WA)

---

E. Player-based Team Distribution

더이상 C번을 풀 엄두가 안 났다. 스코어보드를 보니 E번을 푼 사람이 더 많길래 E번으로 넘어갔다. 문제를 다시 보니 이게 음수를 합치는 경우 점수가 더 커지는 경우가 있겠더라. 되게 당연한 건데, 이걸 놓쳤었다. 그래서 예제를 직접 만들어 가면서 어떻게 합쳐야 할지 생각을 했다. 양수는 일단 한 그룹에 다 몰아넣어야 한다고 생각했다. 그럼 음수는 어떤 것을 합쳐줘야 하는지 고민했다. 당연하게도 0에 가장 가까운 음수를 합쳐야 더 커지겠더라. 그래서 음수를 정렬하고 큰 음수(0에 가까운 음수)부터 보면서 음수를 합치는 경우가 총점이 더 높은지 확인해가면서 양수 그룹에 합쳐주었다. 2번의 WA를 받았다. 그래도 풀이는 맞다고 확신을 해서 조금씩 고쳐서 3트끝에 AC를 받았다!

이 문제도 최근에 그리디 문제를 많이 풀었었는데 덕분에 풀어낸 것 같다. 오늘 기준으로 solved.ac 골드 4 문제인데, 개인적으로 비슷한 난이도의 그리디 문제보단 더 어려운 것 같다.
(02:05 WA)
(02:12 WA)
(02:16 AC)

---

F. 방탈출

C로 돌아가기 전에 F를 읽었다.
과장 1도 안 보태고 보자마자 '어?? 이거 완전 MST잖아?'라는 생각을 했다. 근데 비상탈출구를 처리하는게 뭔가 까다로울 것 같았고, 푼 사람도 거의 없어서 넘어가기로 결정했다. 나중에 보니 생각보다 까다롭지 않더라... 그냥 이걸 풀고 C를 버렸으면 좋았겠다. 끝나고 풀이를 듣는데 비상탈출구를 0번 노드로 생각하고 풀면 그냥 기본 MST문제로 변하더라. 신기했다.


대회에서 이 문제는 3명만 해결했다. 근데 나는 이 문제가 C번이었다면 훨 많이 풀렸을거라 생각한다. 이 문제가 C번이었다면 나는 5솔을 했을지도? ㅋ

---

C. 야바위 게임

그렇게 다시 C로 왔다. 한 10분 동안 코드를 수정해서 제출했는데 이번엔 TLE가 떴다.
(02:22 TLE)


다시 고민이 시작되었다. 그러다가 대회가 10분 정도 남았을 때, 'BFS로 하면 되지 않을까?'라는 생각이 들었다. TLE가 뜬 게 힌트가 되었다. BFS를 이동 횟수만큼 반복하면 될 것 같았다. 그치만 시간이 10분도 남지 않았어서 새로 코드를 짜긴 어려웠어서 기존 코드를 최대한 수정해서 냈고 계속 틀리고 대회가 끝났다.
(02:50 WA)
(02:52 TLE)
(02:53 TLE)
(02:59 TLE)

---

스코어보드 공개

속으로 10등 정도를 예상하고 있었다.
그러면서도 프리즈 이후에 1솔을 추가해서 프리즈 전 6위였던 그룹과 솔브 수가 같아져서 혹시나 했지만 달라지는 것은 없었다.

아 스코어보드 공개하는데 특별상이 있더라. 특별상 받으면 목표였던 SPC 수상을 한 것이니까 좋을 것 같다는 생각을 했지만 받지 못했고, 9등으로 끝났다.

---

주저리

지난 SUAPC나 ICPC와 달리 이번 SPC는 PS를 시작하고 처음으로 수상을 목표로 나름 열심히(?) 준비했던 대회였다. 6등안에 드는 게 목표였는데 많이 아쉽다. 브론즈 문제인 B번에서 뇌절을 많이 했다. 진짜 그냥 주는 문제인데 1시간 17분 만에 맞췄으니 할 말은 없다. 아 근데 틀릴 때마다 보려고 실수노트를 가져갔었는데 거의 보지 않은 점은 많이 아쉽다. 대회에 집중하다 보니 노트의 존재를 잊었었다ㅠ


평소에 알고리즘 분류 탭에서 문제를 골라 풀어서 그런지 새로운 문제를 보면 잘 못 풀어내는 것 같다. 혼자 고민하는 시간이 많이 없었던 것 같다. 아 그리고 평소에 계속 틀리거나 계속 TLE가 뜨거나 하면 질문 게시판이나 구글링을 통해 원인을 찾았었는데, 앞으로는 최대한 내 힘으로 찾아봐야겠더라. 아직은 내가 많이 부족했던 것 같다.


암튼 원래는 내가 말려서 결과가 안 좋다고 생각을 했었는데, 대회가 끝나고 보니 B의 정답률이 18%, C의 정답률이 5%더라 ㄷㄷ; 나만 말린 게 아닌 걸 보고 그냥 이것도 다 실력이란 생각이 든다. B번은 다른 사람들의 정답률이 왜 낮은지 궁금하긴 하다ㅋㅋ. 나랑 같은 실수였을까??


처음에는 6등 안에 못 들어서 많이 아쉬웠었다. 근데 지금 생각해보면 대회에서 골드를 2문제나 해결했으니 잘한 것 같다. 그리고 무엇보다도 정말 재미있었다! 문제 맞히면 풍선도 달아주는데 이게 정말 기분이 좋더라 ㅎㅎ. 이렇게 뭔가 대면으로 한 게 처음이라 더 재미있었던 것 같다. 재미있었으면 된 거 아닐까? 나는 재밌도르수상 했으니 괜찮다!!! ....


수상자분들 축하드립니다!
운영진분들도 고생하셨습니다. 덕분에 재밌었습니다. ㅎㅎ