돌아오는 비행기를 기다리며 작성한 내용이 많았는데, 그 이후 잊고 살다가 이제야 마무리해봅니다.

2019.12.04 (D-2)

1 WA = 5 Push Up 팀과 BFS_BROUGHT_ME_HERE 팀과 동행했습니다. 모두 멋있는 분들입니다.

비행기를 탔습니다. 밤 9시 15분 출발 비행기가 10시나 되서야 이륙했고, 현지 시간 밤 1시에 도착했습니다. 지난주부터 난 감기 몸살 때문인지 5시간 비행시간 내내 자려고 하면 콜록콜록하며 깼습니다. 옆의 팀원은 안쓰러워했고 앞의 모르던 한국인 아주머니께서 불쌍했는지 땅콩캐러맬도 주셨지만 효과는 별로 없었습니다…ㅠㅠ

베트남 다낭 공항에 내려서, 여차저차 예약해둔 유심칩을 찾고, Grab를 통해 택시를 잡아 호텔로 향했습니다. 체크인하니 밤 2시. 배정받는 방은 조금 컴팩트한 디럭스 트윈이었는데, 알고보니 제가 있던 방만 그랬던 거라서 더 슬펐습니다. 아무튼 정신 없이 하루가 정리되어 잤습니다.

2019.12.05 (D-1)

9시 조금 전에 일어나 조식을 먹고 좀 쉬다가 팀 등록을 11시 정도에 했습니다. 베트남 리저널 전통의 인터뷰와 사진 촬영이 있었고, ICPC 티셔츠를 받았습니다. 작년에는 빨간색이었는데 올해는 노란색이었습니다.

12월의 베트남은 생각보다 춥고 바람이 많이 불었습니다. I HATE MATH 후드티를 내내 입고 다니길 너무 잘했습니다. NUT로 이동한 다음 안무 공연을 듣고, 개회식이 있었습니다. 적당히 아호코라식 + 행렬곱 문제를 풀면서 들었습니다. 1시간 정도 설명을 한 다음 연습 세션으로 넘어갔습니다.

작년 베트남 리저널과 여러모로 상황이 달랐습니다.

• 일자형 테이블이 일렬로 배열되어 있지 않고 4개가 정사각형 모양으로 모여 있었습니다.
• 키보드는 버튼이 조금 큰 감은 있었지만, 예상보다 매우 편했습니다.
• 반면 화장실 시설은 심각할 정도로 열악했습니다.

연습 세션은 시간이 계속 왔다갔다하다가 1시간 정도 진행되었는데, 이전 리저널에 나온 바 있는 하-중 정도의 그리디 / 구현 / 인터랙티브 문제로 구성되어 있었습니다. 키보드 테스트도 하고, 2주 전에 풀었던 그리디 문제였는데 말려서 스트레스 받고, push_back을 너무 많이 하면 시스템 자체가 2분 정도 뻑간다는 안 좋은 징조도 발견하였습니다. 제가 당시 컨디션이 안 좋아서 좀 날카로웠는데 때문에 연습 분위기는 그렇게 유쾌하진 않았습니다 ㅠㅠ 반면 Heno World! 팀이 5솔브나 한 건 정말 고무적이었습니다.

연습이 끝나고는 식사를 하러 이동하였습니다. 바람이 많이 부는 식당이었는데, 같이 온 고려대 참가자들이 싫어하는 고수가 좀 많이 뿌려져 있었습니다…전 괜찮게 먹었는데 다른 참가자들에게는 좀 아니었던 모양입니다.

이후 숙소에 8시 30분쯤 도착해서는 올해 Vietnam National 문제를 풀다 잤는데, Easy Probability는 KMP + 행렬곱으로 어찌어찌 AC를 받았는데 Final Exam의 피타고라스 쌍은 뭔 짓을 해도 TLE여서 슬펐습니다. 설상가상으로 팀원 SoulTch가 9시 35분부터 2시간동안 진행된 CF 604에서 말렸습니다. 멘탈 다잡으며 조금 늦게 잤습니다. 대회는 8시에 시작하고, 6시 30분에 나가야 하는데, 취침 시간은 거의 1시였고 처음에 누워서는 기침이 계속 나와서 잠도 못 잤습니다…ㅠㅠ

2019.12.06 (D+0)

결전의 날이 밝았습니다. 아침 5시 30분에 기상하였는데 잠 잔 시간에 비해 기분이 상쾌했습니다. 어제 미리 korea market에서 가서 샀던 스벅 에스프레소 더블샷을 버스에서 마시며 갔으며, 대회장에 안착했습니다. 팀을 밖의 공터에 세우고 한 팀씩 호명해서 들어가는 방식이었는데, 어제도 오늘도 처음 10팀 안에 들었던 것 같습니다. 일찍 들어가서 화장실의 열악함(정말 열악했습니다)도 확인하고, 짐 맡기는 곳도 따로 없다는 것을 확인하고 (팀별 봉투가 따로 없었습니다) 계속 팀원끼리 긴장 풀며 대회가 시작되기만을 기다렸습니다.

문제지를 미리 뒤집어준 채로 나누어졌었는데, ‘Problem M’이라는 텍스트가 보여서 기겁했습니다. 그리고 근처에 네 번째에 위치한 풍선이 특히 많아보여서 D번을 먼저 풀자는 흥미로운 의견이 대두되었습니다. 서울 리저널과는 달리 큰 전광판을 통해 상위 스코어보드는 늘 볼 수 있었습니다.

그렇게 20분 지연된 오전 8시 20분, 대회가 시작되었습니다.

Kattis 쪽 문제는 여기에서, 실 대회 사이트는 여기에서 확인할 수 있습니다.

대회 경과

로그인을 한 다음에 문제가 13개임을 확인하고, SoulTch가 디버그 코드부터 작성하였습니다.

M. Moscow Dream (0:08)

M이 무려 2분에 퍼솔이 나와서 (…) SoulTch가 짜서 맞았습니다.

D. Dating time (0:24, +1)

두 시각 사이에 시침과 분침이 이루는 각도가 0 / 90 / 180일 때의 횟수를 구하는 건데, 일단 풀겠다고 잡았으나 약간 혼란스러운 상태에서 cos 값을 naive하게 비교하는 것으로 접근하였습니다. sin과 cos 용례를 헷갈려서 한 번 틀리는 실수를 하였는데, 예상 외로 이 문제를 1시간 넘어서 푼 상위권 팀들이 많았습니다. D라서 읽힌 속도가 느렸던 것으로 추정됩니다.

지금 생각해보면 이 문제를 굳이 저렇게 풀어야 하나 싶지만, 뇌절이 왔음에도 불구하고 차분하게 넘긴 건 다행입니다.

I. Inspecting Illumination (0:30)

Interactive 문제를 선호하는 SoulTch가 쉽다고 말하더니 정말 바로 풀었습니다.

이후 스코어보드에는 큰 진전이 없었습니다. Patience from Yusuf가 A를 38분에 풀었지만 DP나 행렬로 접근이 어려워 일단 보류하였고, djkim0613은 G를, SoulTch는 L을, 저는 C를 생각하다가 H로 넘어갔습니다.

L. Latin Square (1:19)

latin square 형태는 초기 상태가 valid하면 모든 칸을 valid하게 채울 수 있다는 성질을 예전에 배웠던 것 같은데 전 잘 기억이 안났습니다. 아무튼 SoulTch가 자신감을 가지고 network flow를 짜달라고 했고, 팀노트에서 복붙한 후 짜더니 맞았습니다. 나중에야 알았지만, 홀의 결혼 정리를 통해 존재성을 보일 수 있다고 합니다.

H. Hanjie (1:39)

그 동안 H를 생각하고 있었는데, 잘 생각해보니 한 row 별로 나올 수 있는 가짓수가 길이 6일 때 (1, 1)의 10가지였고, $r, c <= 6$이므로 $10^6$에 valid check는 $36 \times 10^6$에 금방 할 수 있었습니다. 크게 막히지 않고 금방 짰으며 맞았습니다.

이후 슬랙에서 ‘원기옥 모으고 있다’라는 말이 나올 정도로 한동안 AC가 없었습니다. djkim0613은 G를, SoulTch는 K를, 저는 F를 잡고 있었습니다. G가 WA가 중간에 몇 번 나왔었고, F도 짜보았으나 WA가 나와서 곰곰히 생각해보던 시간이었습니다. 이 때 G나 K나 문제를 잘 몰랐고 다른 팀원도 F를 잘 몰랐는데, 지금은 개인 플레이를 하며 문제를 밀어버리는 게 좋을 선택이었다고 생각합니다.

G. Generating Numbers (2:45, +3)

슬랙에서 ‘한 번에 맞기 어려운 문제’로 평가되었던 G였습니다. 예외 처리 하나를 추가한 끝에 djkim0613이 AC시켰습니다. 잠깐 화장실 가려다가 돌아와서 뭐 하나 고친 다음에 내니 맞아서 신기했습니다. 이후 djkim0613은 C에 돌입.

A. Abstract Painting (3:01)

슬랙에서는 이미 함정 문제라고 논의되고 있었는데, 대회장에서 이를 눈치챈 팀은 많지 않았습니다. A는 제가 생각했다가는 말릴 것 같아 더 생각 안 하고 있었는데, 갑자기 djkim0613이 수식 하나로 나오는 것 같다, 5분만에 짜봐서 내보는 건 어떨까라고 말했습니다. 반신반의의 심정으로 그러라고 했습니다. 이 때 SoulTch가 화장실에 있었는데, 셋이 있었다면 이 말을 듣고 어떤 판단을 내렸을지 궁금합니다.

짜서 예제가 나오는 걸 확인하고 내니까 예상보다 오랫동안 채점이 되어서 정말 맞는 거 아냐? 싶었는데 정말 AC가 떠서 서로 박수치고 난리가 났었습니다.

이후 출제진이 의도적으로 제한을 작게 줬다고 밝혔습니다. 인상적인 멘트입니다.

F. Fair Bandwidth Sharing (3:22, +1)

F 첫 제출은 F 퍼솔(2:28)이 나오기 전에 이루어졌었는데, 먼저 최소치만큼 할당하고 이차함수를 관리하는 걸 일차함수의 적분꼴로 바꾸어서, y에 대해 이분탐색을 하는 알고리즘이 틀린 것 같지는 않았습니다. y 제한을 이론치까지 늘리고 발견한 거였는데, 직선의 기울기가 상당히 작을 수 있어서 이분 탐색 횟수가 60번으로는 충분하지 않을 거라는 걸 깨달았습니다. 100번으로 늘리고 제출해보았습니다. 계속 Running일 때 얼마나 심장이 쿵쾅거렸는지 모릅니다. 결국 AC가 떴고, 2등으로 올라서게 됩니다.

프리즈 당시 2등이었지만 A번을 안 푼 팀들이 상당히 많아서 언제 치고 올라올지도 모르는 상황이었고, 아직 K가 남아있어서 불안했습니다. 게다가 코드의 오류로 인해 push_back이 무한히 일어나 컴퓨터가 2분 정도 맛탱이가 가는 게 2번, stack overflow로 맛탱이가 간게 1번 있었습니다. 셋이 이 문제는 잡고 가야한다는데 동의하여 SoulTch는 컴퓨터를 잡고, 나머지 둘은 코드 로직은 잘 몰라도 대칭성이 어그러진 곳이 있는지 계속 확인하며 디버깅을 하였습니다. C를 손절하고 제가 B를 읽은 다음 쉬운 문제라는 걸 간파한 것도 이 때 즈음이었습니다.

K. Keep It Sorted (4:33)

결국 K를 제출했고, 한 번에 맞아서 모두가 환호했습니다. 매우 복잡한 상태전이를 통해 해결하였는데, 푸시업 팀에게 들으니 9! 완전탐색을 돌리면 제한 안에 구할 수 있다고 해서 벙쪘습니다. 어쨌든 AC가 났을 때 나머지 둘은 축제 분위기였고 전 바로 B 코딩에 돌입했습니다.

B가 처음에는 엄청 어려운 문제인 줄 알았는데, 알고 보니 각 바나나를 지나가는 원숭이는 단 한 마리고, 단 한 번 지나갈 수 있었습니다. 그냥 h좌표 스위핑하면 되는 문제여서 불꽃코딩에 들어갔습니다. 대회 종료 1분 30초 전에 예제가 나왔고, 냈으나 WA를 받고 여기까지인가 생각했습니다.

대회 종료

대회가 종료되었고 팀은 축제 분위기였습니다. BOJ 슬랙도 풍악을 올리고 있었습니다. 다른 팀의 패널티를 계산해도 인도네시아 팀 Patience from Yusuf를 제외하고는 역전할 팀이 없었습니다. 같이 고생한 1 WA = 5 Push Up과 BFS_BROUGHT_ME_HERE 팀도 와서 축하해주었습니다.

대회 이후

대회 이후 원래 호이안을 가려고 했던 것 같은데, 일정이 변경되어 사원을 방문하였습니다. 경건하게 사진도 찍고 적당히 잘 걸었습니다. 금방 숙소로 되돌아왔는데, 저와 SoulTch는 토요일 새벽 비행기를 타고 가기로 해 짐을 뺀 상태여서 1 WA = 5 Push Up 쪽 숙소에 가서 BABA IS YOU를 보며 놀았습니다.

6시에 다시 대학으로 이동하여 폐회식을 시작하고, 스코어보드 공개가 진행되었습니다.

Patience from Yusuf 팀은 결국 9솔로 2등을, Powered by Zigui 팀은 3등을 하였습니다. Heno World 팀은 유일한 10솔 팀이었는데, 다시 봐도 정말 강력한 멤버들로 이루어져 있는 것 같습니다 (CF 최고 레이팅 2600+이 두 명이나 됩니다). Send Bobs to Alice와의 박빙승부가 예상되었는데 많이 말린 듯 합니다.

결과적으로는 턱걸이로 월파 티켓을 따냈지만, 이 때만 해도 다낭의 리저널 점수가 최상일 것으로 예상되었기에 3순위인 지구이팀도 갈 수 있는 확률이 높다고 점쳐졌습니다. 기분은 정말 좋았지만, 그보다는 정말 얼떨떨했습니다. 지금도 제가 월파를 간다는 사실이 실감이 안 될 때가 많습니다.

시상식은 정말 금방 끝났고, 만찬이 제공되었는데 다들 맛있는 스테이크를 먹고 싶다고 해서 일찍 빠져나왔습니다. 잠시 대기하고 있을 때 2등팀의 코치와 인사를 할 기회가 있었는데 유쾌한 분 같았습니다. 나와서는 그랩 택시 타서 지구이 팀 세 명이 이런저런 이야기를 하며 시내의 스테이크 집으로 이동했습니다. 맛있었습니다! 스테이크집에서도 한국어 메뉴판이 있을 정도로 다낭엔 한글을 심심치 않게 볼 수 있었습니다.

식사를 마치고 SoulTch와 공항으로 이동했습니다. 다낭의 공항은 인천공항에 비해서는 규모가 상당히 작았는데, 한국인이 빼곡하게 항공편을 기다리고 있었습니다. 가뜩이나 타려는 항공편이 지연되어서 꽤 오랜 시간을 대기해야 했는데, 줄이 줄지 않은 것을 보며 경악했습니다. 이 막간을 이용해서 이 포스트의 대회 파트까지 작성했습니다.

이후는 잘 기억이 안 나네요. 다행히 대회때와 이후엔 감기 기운이 많이 줄어서 체력은 괜찮았지만 정말 많이 피곤했습니다. 비행기도 어찌어찌 탔고 다행히 올 때는 잘 잤으며, 나와서는 한국의 매서운 날씨를 맞보았습니다. 다낭에 있을 때가 공교롭게도 이번 겨울의 가장 추운(영하 10도 정도) 기간 이었습니다. 짐 찾고 공항버스를 타고 집에 도착해서 뻗었습니다.

여담

결과 덕분에 미화된 것도 있겠지만, 적당한 난이도에 괜찮은 문제들이 많았던 세트였습니다. 다만 어느 팀도 풀지 못 한 E나 J중 하나는 없는 게 좋지 않았을까 싶습니다.

이후 월파까지 같이 가는 팀이다보니, 종종 만나서 놀고 팀연습도 하고 PS 이야기도 조금씩 하고 있습니다. 여전히 B는 조금 아쉽습니다.

• 한참 지난 1월 말에 B를 업솔브해보았는데, indexing error 때문에 틀린 거였고 다시 짜본 결과 바로 맞았습니다. 코딩도 30분이 안 걸렸습니다. 10분만 더 있었으면…ㅠㅠ
• B의 난이도에 비해 퍼솔이나 맞은 팀 수가 매우 어려워보이는 것은 무려 4쪽에 걸친 지문 때문이 아닐까 싶습니다. 저런 문제도 읽어보기는 해야 할 것 같다는 교훈을 얻었습니다.
• C는 대충 풀이를 봤는데, 왜 생각 못했을까 싶은 아이디어와 조금 힘들어보이는 구현을 더하면 풀 수 있을 것 같습니다. 베트남에 빈번히 출제되는 수학 계열 문제입니다.

끝으로 같이 선의의 경쟁을 해온 1 WA = 5 Push Up 팀원 @IohcEjnim, @BaaaaaaaaaaaaaaarkingDog, @mixnuts 모두 고생하셨습니다. 그리고 이런저런 연습 속에서도 서로를 믿고 격려해준 @SoulTch @SUDAL 모두 감사드립니다!