제9회 국민대 알고리즘 대회 후기

서론

처음 나가보는 국민대 대회 입니다. 원래 작년에 나가려 했으나 이런 대회는 아무도 언제 열리는지 알려주지 않더라고요? 홍보도 없고요. 결국 신청을 놓쳐 참가하지 못했습니다. 올해는 마감 n시간 전에 지인이 알려줘 겨우 신청 할 수 있었습니다.

 

KOI 2차를 만족스럽게 마치고, 딱히 ps를 하진 않으며 국민대 대회를 기다리고 있었습니다. 

리사콘

여담으로 지인이랑 리사콘을 갔다 왔습니다. 제가 소아온 1기 때부터 리사를 좋아했었는데, 엔젤비트의 최고의 보물, 모든 소아온 ost, 모든 귀칼 ost를 다 해줘서 성불하고 왔습니다.

 

마땅한 사진이 없어 이걸로 대체

코난 극장판도 봤습니다. 코난 잘 모르는데 괴도키드는 좋아해서 적당히 재밌게 봤습니다. 요즘 극장판 퀄리티가 좋더군요.

 

말딸 새로운 시대의 문도 봤습니다. 예고편을 보고 티엠 오페라 오에게 홀려 rttt만 보고 보러 갔는데, 너무 재밌게 봤습니다. MAL 10점 준 애니가 하나 추가되었네요. 미소녀 애니에서 보여줄 수 있는 최고점을 봤습니다. 연출이 진짜 미쳤어요 이건 열혈물입니다... 제가 또 미소녀 열혈 스포츠물을 좋아하거든요(킬라킬, 레뷰 등).

 

디지스트가 디자인이 이쁘더라고요

코엑스에서 개최하는 과기원 합동 입학설명회에 가서 상담도 받고 왔습니다. 4개의 과기원 모두에서 상담을 받았는데, 별로 유의미한 정보를 얻진 못했고, 그냥 다 너무 좋은 학교 같고 합격했음 좋겠고... 그리고 생각보다 가능성이 있어보여서 자소서랑 포폴 열심히 준비할겁니다. 특기자 4개 중 하나는 붙지 않을까요? 4개 다 떨어지면 그냥 정시로 숭컴을 갈 생각...

 

코엑스에 갔기에 말딸을 한번 더 봤습니다. 두번 봐도 재밌네요. 연출이 맛있는 애니라 그런 것 같습니다.

 

봇치더록 특별상영회도 갔다 왔습니다. 적당히 재밌게 봤네요. 극장은 역시 사운드가 좋은듯.

 

그래서 하고 싶은 말이 뭐냐면

처 놀았습니다.

평소에 밖에 안나가던 사람이 이렇게 연속으로 나가서 놀고 노래방 가서 열창하고 이러면 무슨 일이 생길까요?

 

멸망

네. 감기에 걸립니다. 목이 완전히 맛이 가서 처음엔 코로나인줄 알았는데 그건 아니고... 그냥 심한 감기에 걸린 것 같습니다. 몸살기가 심하게 있어서 일상생활을 잘 못했어요.

 

감기 걸린게 저번주 일요일인데, 오늘은 금요일입니다. 아직도 낫지 않았어요.

 

심지어 밤에 잠을 설쳐 2시에 잠들었습니다. 수면을 5시간 정도 한 것 같네요.

 

컨디션은 정말 최악이었습니다. 열나지, 기침하지, 목아프지, 수면부족에... 도저히 생각이라는걸 할 수 있는 상황이 아닌 것 같았습니다. 그래서 제가 세운 전략은 다음과 같습니다.

1. 풀이가 5분안에 보인다면 푼다.

2. 아니라면 데이터가 약하다는 가정 하에 뚫기를 시도한다.

 

국민대 대회는 데이터가 약하다는 소문이 있었습니다. 그리고 테케별 점수가 있는 대회죠. 그래서 저는 뚫기를 전략으로 잡고 가려 했습니다.

 

그러나 작년 대회에는

1. 그냥 하면 됨

2. np라 완탐을 해야하는데 100억이 10초에 도는 문제

3. FFT 기본문제

 

라는 소문이 있었습니다.

일단 FFT를 외우긴 했지만 2번 연속으로 나오진 않을 것 같았고, 이번에도 NP가 나올 것 같긴 했습니다. 

 

대회 전

시오리코 티셔츠

NYPC 티셔츠를 입을까 십덕티를 입을까 하다가 십덕티를 입고 NYPC 후드티를 입어야겠다는 결론에 도달했고, 결속밴드 티셔츠, 러브라이브 티셔츠, 시오리코 티셔츠 중 시오리코 티셔츠가 채택되었습니다. 

 

집에서 대충 11시 정도에 출발하고 국민대에 12시에 도착했습니다. 점심을 먹어야 하는데 주변에 마땅한 식당이 없더군요? 그래서 학식을 먹었습니다.

 

멕시코덮밥, 4500원

일단 키오스크로 식권은 끊었는데, 이걸 어떻게 주문해야하는건지 몰라 물어봤습니다. 그런데 뒤에서 어떤 분들이 "헉... 식권 받는 법 물어보고 있어 저 사람... 신입생인가봐" 하는 소리가 들려 밥을 받고 빠르게 도망쳤습니다. 맛은 그럭저럭 있었지만 식욕이 없던 상황이라 반쯤 남겼습니다.

 

대회장에 도착하고 밖에서 좀 기다리다 입장했습니다. 밖에서 선린인 2명을 우연히 만나 신기했습니다. 에어컨을 안틀어줘서 열사병에 걸릴 것 같았지만 다행히 내부는 시원하더라고요.

 

시오리코 네소를 가져와서 세팅을 할까 고민하다 너무 어그로가 끌릴 것 같아 관두었습니다. 가방에 숨겨두는걸로...

여담으로 대회장 의자가 뭔가 이상했습니다. 이게 대체 무슨 구조지? 아무튼...

 

초반에 오류가 나서 로그인이 안되는 이슈가 있었지만, 일단 로그인에 성공했습니다. 졸려서 뭐라고 해야할 것 같아 펜윅을 짜보는데, 잘 안됩니다. 일단 복잡한 코드를 요구하는 문제를 만나면 안되겠다는 생각을 했습니다.

 

대회 타임라인

문제 유출을 하면 안되어 자세한 설명은 하지 못하는 점 양해 부탁드립니다.

 

1번을 읽었습니다.

https://www.acmicpc.net/problem/23827 의 정답 코드에서 몇글자를 수정하면 맞을 수 있을 것 같았습니다. 1분 정도에 100점을 받았습니다.

 

2번을 읽었습니다.

뭔가 지문이 잘 안읽힙니다. 일단 해석을 해보니 대충 2d 쿼리 점화식 dp 문제로 환원할 수 있고, 스위핑을 하며 세그를 써주면 됩니다. 여담으로 LIS를 이용한 해법도 존재한다고 합니다. 10분 정도에 100점을 받았습니다. 

 

3번을 읽었습니다.

엥 이게 뭐지 흠... 이라는 생각이 들었습니다. 그래서 뭔가 이상한 그리디를 짜니 예제조차 나오지 않았습니다. 문제를 다시 읽어보니 $N \leq 8$? 일단 백트래킹을 짰습니다. 예제는 나오지만 12개의 테케 중 2개만 맞고 나머진 TLE가 나왔습니다. 뭔가 똑똑하게 dp를 할 수 있지 않을까? 라는 생각이 들었지만 제 뇌가 굴러갈 리가 없기에 저는 뚫기를 시도했습니다. 대충 이상한 휴리스틱을 통해 해를 좀 줄였고, 가지도 엄청 쳤습니다. 랜덤을 수정하며 20번 정도 제출하니 12개의 테케 중 6개를 맞을 수 있었습니다. 조금 더 시도하다 하기 싫어서 종료 10분 전에 퇴실했습니다.

 

대회 후

일단 300이 있을 것 같다는 느낌과, 열심히 뚫은 사람도 꽤 있을 거라는 느낌이 들었습니다. 장려는 받지 않을까요? 은 이상을 노리고 있었어서 좀 아쉽긴 했습니다. 솔브닥에서 열심히 수소문해 본 결과 만점 한명과 저보다 점수 높은 사람 한명을 발견할 수 있었습니다. 아마 더 많을 듯 하네요. 

 

도훈님이 학교 후배를 보러 오셔서 인사하고 얘기를 조금 했습니다. 대충 3번에 NP가 말이 되냐 어쩌구 하면서 징징댔던 것 같습니다 ㅋㅋ. 종이님이 대회를 치진 않았지만 저를 보러 왔다고 하시더라고요? 그래서 선린 친구 한명, 도훈님, 종이님, 도훈님 후배, 이렇게 같이 밥을 먹으러 갔습니다. 정확히는 도훈님이 저를 유기해서 종이님이랑 선린 친구랑 밥을 먹으러 갔는데, 그곳에 도훈님이랑 도훈님 후배가 왔습니다. 

 

햄버거는 적당히 맛있었습니다. 근데 뭔가 술집 느낌? 아무튼 잘 먹었습니다.

 

비싸서 못간 오케콘...

죽을뻔

친구가 홍대에 가자고 해서 애니메이트에 갔다 노래방에 갔다 오락실 가서 태고를 조금 하고 집에 도착했습니다. 목이 아픈데 노래방에 가니 죽을 것 같았습니다. 그래도 열심히 안부르면 아쉬우니 열심히 부르기는 했습니다. 대충 undead랑 비바해피랑 이런거 불렀습니다.

 

결론

장려는 나오지 않을까요? 국민대는 장려를 퍼준다고 하던데... 믿고 있겠습니다. 제가 ps를 조금 늦게 시작해 특기자 원서에 끼워넣을만한 상이 부족해서 뭐라도 받아야 합니다. 분량은 채워야지... 

대회 친건 뭐 그럭저럭 할 수 있는만큼 한 것 같아서 만족스럽습니다. 도훈님도 보고 종이님도 보고... 재밌었네요. 뭔가 중학생때부터 인터넷 친구를 많이 만나다보니 어색해하지 않고 대화를 하게 되는 능력이 생긴 것 같습니다. 좋은걸까요?