[알고리즘] 서울대학교 SCSC 프로그래밍 경진대회 후기

https://www.acmicpc.net/board/view/143175
https://scpc.p-e.kr/
 
서울대학교에서 외부인도 참가할 수 있는 오프라인 대회를 개최했다! 당연히 참을 수 없어서 보자마자 참가신청을 넣었고 대회에 참여했다.
 

Before Contest

서울대는 중학생때 숙제하러 한 번 오고 처음오는데 이제 와서 보니 정말 컸다. 학교 안에서 호기롭게 혼자 버스 안타고 걸어가다가 땀 흘리면서 강행군을 했다;; 서울대에서 연강걸리면 버스타고 다녀야되는 것 같다. 산으로 뒤덮여있어 정기를 받기 좋았던 것 같다.

멀리서 보이는 샤 정문

처음 신청할 때 생각없이 Div 1로 신청했는데 대회 3일 전쯤에 Div 1은 정말 어려우니 Div 2로 바꿀 수 있는 마지막 기회를 준다는 문자를 받았다. ㅋㅋ 이 문자를 받고 겁쟁이가 돼서 후다닥 Div 2로 바꿔서 참가했다. 그렇게 Div 2로 들어와서 보니 한 150명 정도 참가한 것 같다. 대회 시작 전에 운영진 분들이 기념 품과 계정을 나눠주는데 종이에 써 있는 것을 일일히 찾아서 나눠주다보니 시간이 지체됐다. (물론 정렬하고 이분탐색 하셨겠지?) 그래서 대회가 15분 미뤄졌다. 많이 고생하신 것 같다..
 

SCSC 기념품들

 

Contest

그래서 대회는 2시 15분부터 시작했고 Div 2는 난이도 순으로 정렬돼있어서 A번부터 열어서 봤다. 평소에 백준 대회를 하면 퍼솔을 자주 먹었는데 노트북 환경 + 손떨림 이슈로 못먹었다 ㅠㅠ
 
00:07 A [solved!! + 3]
A번부터 절었다. A번이니까 날먹할 수 있나? 싶어서 뇌빼고 코딩하다가 2번 틀리고 천천히 분석해서 풀었다. A번 치고 꽤 복잡했던 것 같다.
 
00:13 B [solved!! + 2]
B번도 약간 말렸다. 그리디한 전략으로 시도했으나 틀리고 이후에 제한이 작은 것을 캐치하여 빠르게 브루트포스 돌려서 해결했다.
 
00:18 C [solved!! + 1]
C번은 너무 많이 본 그래프 문제여서 손쉽게 해결했다. 파이썬이라 탐색하기 싫어서 분리집합으로 대충 해결했다.
 
01:21 F [solved!! + 1]
C를 해결하고 D를 봤는데 제일 약한 확률문제가 나왔다. (수능볼 때도 확통을 제일 못했다) 확률에 약하기도 하고 사다리게임도 처음보는 유형이어서 한 30분 고민하다가 답이 안나와서 넘겼다. 넘기고 E로 가니 딱보니 내가 제일 못하는 게임 + DP유형이라 넘기고 그나마 할만한 그래프문제인 F로 갔다.
$N, M$이 $200\,000$대에 최단경로를 구하라는 걸 보니 다익스트라 쓰는 것임을 빠르게 캐치했고 친절한 예제 그림을 보니 다익스트라 돌리며 나오는 현재 위치와 다음 위치를 연결하다 보면 트리가 하나 나온다. 각 노드에 트럭이 몇 대 지나가는지 DP로 적절히 구하면 풀 수 있는 문제였다. 무사히 원트에 해결했다.
 
01:36 D [solved!! + 2]
F 풀고 나서 G, H는 솔브가 너무 안나와서 D로 돌아갔다. 네이버 사다리타기를 여러번 만들어보고 로컬에서 사다리타기 시뮬레이션 돌리고 있다가 번뜩이는 아이디어가 떠올랐다. DP로 접근해보니 갑자기 길이 보이더니 예제가 통과했다. 
현재 사다리의 왼쪽에 길이 생길 확률, 오른쪽에 길이 생길 확률, 현재 사다리에 연결되지 않은 곳에 길이 생길 확률을 각각 나누어 DP를 돌리니 답이 나왔다. 3번 케이스를 처리하지 않아서 한 번 틀렸다. (이 케이스가 없는 나쁜 예제 ㅜㅜ)
 
남은 시간은 간식먹으면서 멍때리고 있다가 H번이 3진 OR문제여서 트라이인가? 하고 시도했다가 얻어 맞고 대회가 끝났다. 끝나고 에디토리얼보니 DP였다. 
노트나 태블릿을 안들고가서 다 머릿속으로 풀 수 밖에 없었는데 있었어도 더 풀지는 못했을 것 같다.

화질구지네요

결론은 5솔, 14등으로 마무리했다!
 
14등은 상품이 문화상품권 1만원이다. 근데 시상하면서 갑자기 상품권이 사라졌다는 소식이 있었다. 갑자기 상품을 없앤다고? 라고 생각하며 슬퍼했는데 실제로 분실한 것이어서 현장에서 지급을 못 한다는 것이었다. 그래서 연락처를 제공하고 나중에 받게 되었다 ㅋㅋ
Div 1은 썰 들어보니 A번 말고는 플래티넘 이상의 어려운 문제들로 이루어져 있었다고 했다. Div 2로 도망간게 최고의 선택이었다. 
 

After Contest

SCSC에 건국대학교 Alkon 부원들이 많이 왔다. 만나서 저녁을 먹고 알고리즘 얘기를 한참 했다. 요즘은 알고리즘 많이 안하다보니 이런 얘기에 기가 빨린다 ㅠㅠ. (옛날의 나를 보는 것 같군)

샤브샤브 무한리필집을 갔는데 가격도 괜찮고 맛도 좋았다. 
 
나갈 수 있는 대회가 몇 없는 늙은이인데 오랜만에 온사이트 대회를 해서 너무 좋았고 아직 감은 잃지 않은 것 같았다. 상당히 큰 규모였는데 외부인도 참가할 수 있도록 대회를 개최한 운영진들이 대단하게 느껴졌다. 고생하셨습니다!! 짱짱!!