5월 16일에 있었던 SCSC 대회를 치고 왔다. '소로휴가10만원보내면수상시켜준댔어요'로 참여했고, Div. 2에서 13등을 했다.
대회 후기만 딱 쓰면 재미가 없을 것 같아서, 그 전후의 이야기들도 풀어보고자 한다.
5월 9일
PNUPC(부산대 대회)를 쳤다. 오픈콘 현장 참여자들 중 꼴지였다.
아무리 채점기 이슈가 있었다지만 너무 말아먹었던 것 같다.
일주일 뒤 SCSC에서는 제대로 치겠다고 다짐하며, 한 주동안 PS를 좀 하기로 다짐했다.
그날 저녁 지하철에서 폰코딩으로 앳코더 ABC 457을 돌았다.
5월 12일
ARC 219 버츄얼을 돌았다. A 말리고 B 잘 풀고 C 말리고 D 잘 풀었다.
5월 14일
AWC 0068 Beta 버츄얼을 돌았다. 수업시간에 몰래 돌았다.
C가 자료구조라서 말렸다. D를 풀고 E를 읽자마자 풀이가 떠올랐는데 수업이 끝나서 그냥 안풀었다.
5월 15일 (대회 전날)
대회 전날인만큼, 컨디션 조절을 해야지!! 라고 다짐함.
이 날 소화해야 했던 일정이...
과외 (새벽 12시 반 ~ 새벽 2시 반)
Pre-lab 리포트 작성 (기한: 오후 1시까지)
Post-lab 리포트 작성 (기한: 오후 1시까지)
화학전공실험 수업 (오후 1시 ~ 실험 끝날 때까지)
RUN 스터디 연사 (오후 7시 ~ 오후 8시)
친구 생일 기념 술 마시러 가기
그래서 아침 8시까지 과외랑 과제들을 했고, 3시간 반정도 자고 마저 과제한 다음 화학전공실험 수업을 들으러 갔다.
이 과목은 오후 1시에 시작해서 실험이 끝날 때까지 실험하는 과목이다. 보통은 오후 4~5시 쯤에 끝나니까, 실험 끝나고 기숙사에서 잠깐 낮잠잤다가 저녁에 일어난다는 계획을 세웠다.
그런데 이게 5시간 반이나 걸리네? 오후 6시 반에 끝났네???
너무피곤했지만...결과물이 예쁘니 만족.
불행 중 다행으로, 스터디가 취소되어 저녁 7시의 일정이 사라졌다.
그래서 친구들이랑 같이 저녁밥을 먹고 내 단골 바에 갔다.
노가리를 까고 홀덤을 치다 보니 시간이 너무 잘 가버렸다!
새벽 2시를 조금 넘겨서 잠들게 되었다...
5월 16일 (대회 당일)
기차를 제때 구하지 못해 아침 7시 20분 기차를 타야 했다. 나랑 loreips, mythofys가 아침 6시쯤부터 일어나 함께 이동했다.
기차역에서 삼각김밥과 알로에 음료로 아침을 때웠다. 냠냠
광명역에서 mon_de2738님의 일행과 합류하여 서울대입구역으로 갔다.
이때 시각이 오전 9시라서 대회장으로 바로 가기엔 너무 일렀다.
그래서 주변의 교보문고에서 시간을 때우기로 했다.
만년필 체험 겸 mythofys 찬양을 하고 알고리즘 책 보면서 SCSC 벼락치기 함
mon_de2738님 일행과 다시 헤어지고, 얼마 전 sorohue님께 추천받은 냉면집을 찾아갔다.
평양냉면은 처음이었는데 굉장히 내 입맛에 맞았다.
오픈런을 하지 않아서 점심특선을 시키지 못해 아쉬웠다. 다음에 또 가야지.
냉면을 야무지게 먹고 다시 서울대로 ㄱㄱ
이제부턴 진짜로 대회 이야기를 해보자.
SCSC 대회는 참가자들의 실력에 따라 세 개의 division으로 나누어 진행된다는 특징이 있다.
내 주변 사람들은 대부분 Div. 1으로 납치당했으나, 나는 Div. 2에도 참가할 수 있어 Div. 2를 신청했다.
충분히 상위권을 노려볼만한 대회이다.
이번 대회에서의 내 목표는 크게 두 가지였다.
1) 아무 문제나 퍼솔(first solve)하기
2) 순위상 받기
퍼솔을 하면 에디토리얼에 내 닉네임이 들어간다. '소로휴가10만원보내면수상시켜준댔어요'를 박제하고 싶어서 1번 목표를 세웠고,
이 닉네임을 달고 Div. 2에 가서 수상을 못한다? 이건 내 멘토인 sorohue님한테 갈궈져도 할 말이 없기에 2번 목표를 넣었다. 왜냐하면 순위상을 무려 40등까지 주는 대회이기 때문...
(닉네임은 내가 대회에 10만원 후원을 해서 이따구로 지은거다)
대회 전
참가 등록을 하고 기념품을 받은 후, 안면을 튼 적있는 사람들과 인사를 나눴다. 후원자 혜택으로 싸이버거 세트를 준다길래 받으려고 했지만, 그 시점이 대회 시작 직전이거나 직후라서 (기억이안나요) 문제를 좀 풀다가 받으러 가기로 결정했다.
평소처럼 VSCode를 왼쪽 절반, 문제 창을 오른쪽 절반에 띄워놓고 잠시 기다리자 대회가 시작되었다.
0:00 (대회 시작)
사전에 A가 가장 쉬운 문제라는 공지가 있었다. 따라서 나는 바로 A를 스킵했다. 모두들 A를 먼저 잡을테니 그동안 다른 쉬운 문제를 먼저 찾아서 퍼솔하겠다는 생각이었다. 기왕이면 내 이름이 들어간 문제를 퍼솔하고 싶어서 (이것도 후원자 혜택이다) 모든 문제를 훑어보았지만 어디에도 내 이름이 보이질 않았고, 쉬운 문제를 찾아 꽤 헤맸다. 10분 정도가 지났을 무렵 문제 이해가 비교적 쉬운 G를 잡기 시작했다.
승리 전략이 바로 떠오르진 않았으나 몇 가지 상황을 만들어놓고 게임을 직접 해보니 점점 감이 잡혀왔다. 단순한 홀짝성 + 한 가지 예외처리면 충분하다고 확신을 했고, 구현했으나 WA를 받았다. (0:30) 대체 뭐가 문제인지 코드를 뚫어져라 보던 와중 G의 퍼솔이 등장했다. (0:34) 근데 알고보니 인덱스에 사소한 실수가 있어서 이전에 제출했던 코드에서 딱 한 글자만 바꾸니까 맞더라... 너무 아쉬웠다.
0:39 (G solved)
40분 가까이 지난 시점에서, 또 다른 문제의 퍼솔을 노리러 가는 것은 위험부담이 컸다. 당장 1등이 4솔을 하고 있는 상황이었다.
그래서 퍼솔은 포기하고 스코어보드를 따라가기 시작했다. 우선 가장 쉬운 문제라고 했던 A를 열었는데... 당황스러웠다. 지문이 너무 길었다.
근데 차근차근 읽다보니 리프만 잘 구해주면 되는 실버급 문제이길래 슥슥 짜서 맞췄다.
0:47 (A solved)
그다음으로 많이 풀린 두 문제는 F와 J였다. F는 극초반에 모든 문제들을 훑어보는 과정에서 이해가 잘 되지 않아 건너뛴 문제였는데, 다시 읽고 나이브를 돌려보니까 규칙이 뻔히 보이더라. 같은 숫자만 반복될 줄이야...
0:54 (F solved)
바로 J를 잡았다. 많은 사람에게 풀린 문제였기에 단순한 패턴이 있을 것이라 짐작하며 문제를 읽었다. 우선 첫 턴에 자신의 명찰을 알아내는 사람을 자명하게 솎아내면, 그 다음 턴에 나머지 모든 사람이 자신의 명찰을 알 수 있을 것 같았다. 믿음의 제출을 날렸다.
1:00 (J solved)
20분동안 3문제를 풀었다! 초반 스퍼트가 나쁘지 않다고 생각하며 다음으로 풀 문제를 찾아 나섰다. 스코어보드를 보니 C, D, E가 풀려있었지만 세 문제 모두 푼 사람이 많지 않았다. 대회가 끝나기 전엔 모두 풀어야 될 문제같아서 모두 읽어보았다.
C가 쉬운 문제인줄 알고 각 문자의 등장 횟수만을 이용해 대충 짰다가 틀렸다. (1:09) C를 고민하며 싸이버거 세트를 수령했고, 잠깐의 휴식을 가지며 세 문제 모두를 얕게 고민했다.
C에서, 특정 문자열이 최대한 많이 등장하게 하기 위해서는 접두사와 접미사의 공통되는 부분을 최대한 재활용해야 한다는 것이 떠올랐다. 이건 KMP의 실패함수를 이용하면 되는건데, KMP 문제인 것 치고 너무 많은 사람들이 풀었길래 이게 아닌가 싶어서 잠깐 헤맸다. 구현 찐빠나서 2번 더 틀린 후에 맞췄다.
1:44 (C solved)
E를 봤다. 상자를 소모 마력 순으로 정렬한 후 접근하는 전략이 최선일 것이라고 생각했다. 이렇게 그리디를 전제로 깔아두고 케이스를 나눠 식을 잘 써보니 나름 간단하게 정리되었고, 7줄짜리 코드를 내서 맞았다.
2:09 (E solved)
D가 쿼리 문제라서 미뤄두고 있었지만, 이젠 진짜 풀어야 했다. 또 이상한 자료구조 범벅인거 아닌가 싶었지만, 순간 내 머릿속을 스쳐지나가는 한 단어가 있었다. '누적 합'.
진짜 무슨 근거인지는 모르겠지만 이 문제가 누적 합을 쓰는 문제라고 반쯤 확신한 상태에서 풀이를 찾기 시작했다. 처음엔 그림을 직접 덧칠해가며 접근했지만 빠르게 WA를 받고 기각. (2:18)
D를 고민하며 다른 문제들을 구경하다가 L이 해 구성하기 문제라는 것을 알게 되어 정독하였다. 직후에 바로 '그냥 이진 트리 만들면 될 것 같은데?' 라는 생각을 하여 패드에다가 대강 그려놓고 다시 D에 집중했다.
같은 색이 이어져있는 것들을 블록으로 보고 각 블록을 처리하기 위한 최소 덧칠 횟수를 누적 합으로 전처리했다. 이후 주어지는 구간이 블록에 걸쳐있는 경우만 따로 고려해주고, 구간이 블록을 완전히 포함하면 누적 합으로 빠르게 계산했다.
얘도 구현 찐빠나서 한 번 더 틀렸다.
2:48 (D solved)
7솔을 했고, 7등에 올라서게 되었다!! 이 시점에선 1등도 7솔이었기 때문에 하나만 더 풀면 키보드 수상은 거의 확정인 상황. 아직도 다 먹지 못한 싸이버거를 마저 먹으며 다시금 풀 만한 문제를 탐색했다. (구현 도중엔 집중하느라 먹을 틈이 없어서 채점 큐 돌아가는 동안만 야금야금 먹고 있었다)
참가자들이 H, I, L에 시도했다가 틀린 흔적이 보였다. 내가 푼 7문제를 제외한 나머지 모든 문제에 아직 퍼솔이 나오지 않았기 때문에, 무엇이 제일 쉬운지 확신할 수 없었다.
그래서 앞서 풀이의 틀을 잡아놓은 L에 나머지 모든 시간을 부어보기로 했다.
이진 트리의 리프를 1~n으로 잡는 것만 생각해놨기에 아직 많은 디테일을 더 떠올려야 했다. 우선 k가 log n보다 커서 이진 트리만으로는 부족한 경우엔, 루트에 일자 트리를 매달아 시간 지연책을 쓰면 된다. 노드의 개수가 2048개를 넘어갈 것 같네? 이진 트리를 구성하는 노드는 1~n을 재활용하자. 포화 이진 트리로 만들어도 충분히 가능하다... 뭐 이런 식으로 풀이를 구체화했다.
그런데 구현이 병목이었다. 단순히 트리를 구성하는게 아니라 각 노드의 세 가지 값을 지정해야 되는 상황이니 머리에 쥐가 나더라. 어찌어찌 하여 1300B짜리 코드를 짜서 냈지만 틀렸다. (3:40) 예제부터 틀렸다길래 예제를 그려가며 차근차근 디버깅했고, 하나 고칠때마다 제출하며 패널티를 차곡차곡 적립했다. 더 이상 패널티는 중요하지 않았다. 얘를 맞추기만 하면 된다는 마인드였다.
대회 종료 8분 전, 2개의 채점 데이터를 제외한 모든 데이터에서 AC를 받았다. 무조건 엣지 케이스에서 틀렸을 것이라는 확신을 가져 이것저것 예제를 집어넣어보니 n = 2인 경우가 제대로 출력되지 않고 있었다. 급히 n = 2인 경우를 일반화하여 예외로 빼고 대회 종료 15초 전, 종료 2초 전에 두 개의 코드를 제출했지만...
두 코드 모두 WA를 받았다.
주변에서 박수 소리가 들려왔다.
4:00 (대회 종료)
스코어보드가 프리즈 된 직후의 내 등수는 10등. 딱 키보드를 받을 수 있는 커트라인이다.
그런데 패널티가 꽤 큰 편이었던 나를 아무도 못 넘을리는 없을 터. 키보드는 물 건너간 상황이었다.
그것보다도 그냥 L을 풀지 못한 것에 굉장히 화가 났다. 풀어야 되는 문제였고, 시간이 조금만 더 있었더라도 무조건 풀 수 있을 것 같았다. 옆자리의 loreips는 1시간 반동안 I에서 파혐당하고 있었다며 억울함을 토로했다.
온라인에서 만난 분들과 노가리를 까며 돌아다니다 보니 어느덧 Div. 1도 다 끝났다. mon_de2738님이 내 옆으로 오셔서 L(=div1J)을 풀지 못했다며 한탄했다. 나도 나의 다이나믹한 디버깅 과정을 늘어놓고 있었는데, mon_de2738님이 'F가 n 이하여야 한다'라는 조건이 있다는걸 나랑 이야기하면서 알게 되었다고 한다. 바로 몇 줄 고치니까 AC 뜨는거 보고 아쉬워하셨다.
혹시 나도 지잘읽 이슈가 있었나? 하고 지문을 다시 보니까, k가 n 이하네? 그 말인즉슨 n = 2이면 k는 무조건 2일 수밖에 없다. 애초에 예외처리를 해야하는 경우가 단 한 가지였던 것이다. 저걸 하드코딩해서 바로 제출해보니...
음.
진짜 5분만 더 있었어도 풀었겠는데?
속으로 수없이 많은 바르고 고운 말들이 오갔다^^
이후 스코어보드 공개 및 시상식이 있었다.
그런데 맞은 문제만 노란색으로 표시되고, 틀린 문제는 그냥 빨간색으로 떠있었다. 심지어 division이 3개라 스코어보드를 확확 넘기길래 그냥 딴짓했다. 운영진분들 죄송합니다
나는 13등이었고, 상품으로 네이버페이 2만원을 받게 되었다.
여담으로 내 닉네임을 보고 사회자께서 10만원 주고 2만원(11~20등 상품) 받았으니 8만원 손해라고 하시더라.
근데 교통비 식비 숙박비 합치면 거의 20만원 털렸을걸요 ㄱ-
스코어보드 공개 중 탈주를 친 후 rongrongbot님이 주최하신 옷살팟에 꼈다. alreadysolved, mythofys, jkrt2, kky085437, gs12117, jhuni님께서도 함께 참가하여 8인팟이 되었다. 나랑 mythofys, jkrt2, kky085437 테이블에서는 아래의 4인 세트 메뉴를 시켰고, 인도식 요리는 오랜만이라 그런지 되게 만족스러운 식사였다.
시간이 오후 9시가 다 되어가길래 넷이서 앳코더 폰코딩으로 내기를 하기로 했다.
C++ 사용자는 A번, 파이썬 사용자는 B번 문제를 잡고 가장 늦게 푸는 사람이 아이스크림을 사주는 것이었다.
나는 앳코더 레이팅을 크게 신경쓰지 않고 사는 사람이라 그냥 rated로 참가했다.
근데 2분대에 B, 4분대에 A, 6분대에 C를 풀어버림 개꿀
그래서 아이스크림 언제 사주시나요 (누가 꼴지인지도 모름)
나랑 mythofys는 다음날에도 서울에서의 일정이 있었기에 둘이서 주변 찜질방에 갔다.
코포를 칠까말까 하다가 그대로 뻗어서 잠들어버렸다...
5월 17일 (대회 다음날)
mythofys가 벚꽃컵에 참여해야 해서 오전 10시 반쯤에 찜질방에서 나왔다.
나는 toycartoon님이 주최하는 밥약?에 참여하기 위해 홍대쪽으로 갔다. 약속 시간보다 한시간 반정도 빨리 도착해서 카페에서 블로그를 쓰기 시작했다.
이후 toycartoon, nflight11, rlatjwls3333, terrasphere, jshyun912님을 만나 라멘을 먹으러 갔다.
aerae님이 합류하여 과자와 탄산음료를 무제한으로 주는 보드게임카페에 갔다. (sorohue님은 게임하던 도중에 오셨다)
우노, 머핀타임, 5초준다, 텔레스트레이션 등 이것저것 하며 놀았다.
난 텔레스트레이션이 ㄹㅇ 꿀잼이었다. (대충 갈틱폰 보드게임 버젼) 다들 ps를 하는 사람들이다보니 알고리즘이나 백준 문제같은 것을 써도 모두가 즐길 수 있었다. ps러들 정모에선 이걸 꼭 하길 바란다.
보드게임만 5시간을 넘게 해버려서 저녁 시간이 되어버린 바람에 무한리필 고깃집에 갔다. 여러 이야기가 오가며 즐겁게 밥을 먹다가, 기차 시간이 다가와서 먼저 자리를 떴다. 재미있었습니다~
맺음말
이번 SCSC 대회는 ICPC 2025, 세미게임컵 4, PNUPC 2026에 이은 내 4번째 오프라인 대회였다.
13등을 찍으며 내 오프라인 대회에서의 최고 퍼포먼스를 보여줬지만, 기쁘기보다는 아쉬움이 더욱 짙게 남았다.
여름에는 UCPC, SCPC, LGCPC가 기다리고 있다. 제대로 칼을 갈고와서 더욱 성장한 모습을 보여주리라 다짐한다.
이번 대회에서의 명찰 및 후원자 카드 사진과 함께 이 글을 마무리하겠다.
