ICPC Seoul Regional 2019 후기

공식 스코어보드

스코어보드는 여기서 볼 수 있다.

 

5, 6위팀과 페널티 4분이라는 근소한 차이로 전체 4등 / 90팀으로 대회를 마무리했다. 예선 본선 모두 4등이다.

팀원은 imeimi, TAMREF, jhhope1. A Bus With No Drivers 팀처럼 컴공과가 한 명밖에 없는 팀이다 ㅋㅋ

 

팀 전략, 사전 연습, 팀노트

즈홒(jhhope1)은 풀이를 내는 능력이 뛰어난 데 비해 아직 구현이 익숙하지 않았고, 나는 코딩이 빠른 편이지만 풀이를 잘 못 만들었다. imeimi는 단점이 없다. 그냥 이멘이다 ㅋㅋㅋ

 

그래서 즈홒은 코딩을 잡지 않았고, 내가 Soulless Coding Machine 역할을 하면서 즈홒과 이멘이 주는 풀이를 구현하는 위주의 전략을 사용했다. 레드코더 2 ~ 2.5명 정도가 팀에서 낼 수 있는 최대 아웃풋이었다고 생각한다.

 

연습은 거의 안했다. 셋이 모여서 한 팀연습은 한 번밖에 없고, 3~4번 한 연습은 나와 즈홒 2인팀으로 참여해서 내 코딩 능률을 높이고 + 의사 전달을 정확히 하는 걸 연습했다. 이메이미가 풀이를 잘못 전달하는 경우는 없더라.

 

팀노트는 더불어민규당 것을 이메이미가 커스터마이징했다. 이멘이 쉽게 구현할 수 있는(...) Link-Cut 같은 걸 빼고 Perfect Elimination Ordering같은 걸 추가했다는데 그걸 제대로 활용할 수 있는 사람이 이멘뿐이어서 딱히 관여하지 않았다.

 

대회 복기

초반 (~1시간)

 

처음에 내가 vimrc 세팅과 템플릿을 입력했고, 그 사이에 이멘이 A를 풀어서 던져줬다. 9분 AC.

 

이메이미가 그 사이에 B를 풀었는데 (ㄷㄷ) 빨리 완성할 수 있는 문제가 아니었다. 하지만 내가 읽은 문제가 없었고 즈홒은 지문이 이상하고 긴 D를 읽고 있었기 때문에 선택지가 없었다. 코딩을 스왑하고 I ~ K를 읽었다.

 

이메이미가 코딩 실수로 고전하는 사이에 I 풀이가 나왔고, J의 사풀이 나왔다. 그런데 I는 나름 파라메트릭 + 그리디까지 해서 머신을 15~20분 정도 잡아야 할 것 같았고, J가 스코어보드에서 속속 풀리고 있었기 때문에 내 직관이 맞다고 생각하고 J를 잡았다. ㅋㅋ!

 

J 사풀을 열심히 코딩했는데 당연히 틀렸고, 그 사이에 이멘이 B를 고쳐서 맞았다 (31분). 퍼솔!

J를 즈홒에게 넘기고 I를 코딩했는데 또 틀렸다! 알고리즘이 틀리지 않은 이상 틀릴 곳이 많지 않은 문제였고, 그래서 10분 정도 알고리즘을 의심하다가(...) J 풀이로 넘어갔다.

 

그 사이 이메이미가 L을 밀었고 (59분), 그 동안 즈홒에게 J 반례를 몇 개 받아서 같이 생각뇌절하고 있었다.

와중에 불현듯 I에서 이분탐색 범위를 잘못 생각했다는 걸 알았고, 이메이미의 제출과 동시에 AC. (60분)

 

그래서 1시간 4솔 + 남들 다 푸는데 모르겠는 J가 초반부 상황이었다.

아마 20위권 근처였던 것 같은데, 쌓일 페널티들을 생각하면 굉장히 부진한 성적이었다.

 

중반 (1 ~ 3시간)

 

I가 맞는 걸 확인하고 나서 다시 J로 돌아와서 뇌절을 계속했다. 될 턱이 없는 \(O(n)\) DP를 계속 붙잡고 식을 개선하고 있었는데, 잘못된 가정에서 빠져나올 생각은 못했다. 발전 없이 WA만 3번.

 

이메이미가 H를 맞고 나서 (85분) 상황은 더 급해졌다. J를 풀지 못하면 상위권에 갈 수가 없었다!

 

J에서 맞는 풀이를 만들어낼 자신이 없었고, 그냥 이메이미가 설명해준 K를 짜러 갔다. 지금 생각하면 당연한 관찰인데 이때는 이해도 못하고 그냥 짰다 ㅋㅋㅋ

 

정답을 보장하는 방법이 \(\mathcal{O}(n^{4})\)밖에 생각이 안 났다. \(n = 100\)인게 영 마음에 걸려서 야매로 일부 경우만 해보는 \(\mathcal{O}(n^3)\)을 짜다가 두 번 틀렸다. 지금 까보니 데이터 개수만 265개였으니 어림도 없었겠다 싶다. 걱정 반 기대 반으로 \(\mathcal{O}(n^{4})\)를 짜서 냈는데 AC가 떴다. (141분)

 

그 사이에 이메이미가 한숨을 쉬면서 맞는 J 풀이를 만들어왔다. 로컬 실수를 몇 번 한 뒤 AC. (153분)

 

3시간 기준으로 7솔. 10위권 정도로 돌아왔다.

 

후반 (3 ~ 5시간)

 

사실상 상을 가져다준 시간대다 ㅋㅋㅋ

K를 짤 때쯤부터 이메이미가 G를 고민하기 시작했는데, 같이 생각하다가 도움이 되지 못해서 이메이미가 혼자 풀었다. 눈물을 흘리면서 lower_bound가 떡칠된 코드를 짜더니 AC를 받더라... 그는 'imeimi'. (196분)

 

그 사이에 D와 E(...)에 고통받던 즈홒을 데리고 F를 읽었다. 문제에서 점수를 주는 기준이 너무 특이해서 뭔가 있겠다 싶었다.

 

하지만 이  두 명이 늘 그렇듯이 문제를 또 잘못 읽고 30분을 버린다. 그제야 정신을 차리고 예제랑 대조해가며 문제를 읽었다. F가 요구하는 문제는 주어진 점으로 만들 수 있는 (a) convex한 사각형 개수와, (b) 넓이가 최소인 사각형 개수를 counting하는 것이었다.

 

하지만 이 듀오가 문제를 또 또 잘못 읽어서 (a)가 소거되었다 엌ㅋㅋㅋㅋㅋㅋ 정확히는 점수 기준을 잘못 계산했다.

그래서 (b)만 열심히 풀었고, 즈홒이 그리 어렵지 않게 \(\mathcal{O}(n^{3})\) 풀이를 완성했다.

 

이메이미가 (다행히도?) G를 짜느라 컴퓨터를 놓지 않았고, 그 사이에 풀이를 검토하다가 문제를 잘못 읽었다는 사실을 알았다. 이제 (a)도 풀어야 했다!

 

그런데 (b) 풀이가 완성된 상태에서 (a)를 보니 관찰하기 더 쉬웠다. 내가 연립 방정식으로 문제를 푸는 아이디어를 냈고, 이메이미가 G를 맞을 때에는 (a), (b)를 모두 \(\mathcal{O}(n^3)\)에 푸는 풀이가 완성되어 있었다.

 

\(n = 1000\) cubic을 1.7초 안에 우겨넣을 상상을 하면서 이메이미에게 풀이를 들고 갔더니 바로 빠꾸를 먹었다. ㅋㅋ!이메이미가 풀이를 듣고는 JOI bulldozer와 같은 방법으로 복잡도를 \(\mathcal{O}(n^{2}\lg n)\)으로 내렸다. 'imeimi'.

 

그런데 우리 팀은 연습때부터 기하 문제를 단 한 번도 맞은 적이 없었다. 그래도 풀었으니 맞아야지!

기하 코딩을 가장 빨리 할 수 있는 나를 뒤에서 이메이미가 조종하며 페어 코딩을 했고, 로컬에서 몇 번 틀리더니 바로 AC가 나왔다! (265분).

 

F를 맞은 뒤로는 사실상 노는 분위기였다. 증명이 안 돼서 코딩큐 저편에 밀어둔 즈홒의 D 풀이를 채찍을 맞아가면서 코딩했지만 예제조차 나오지 않았고, 두 번 틀린 뒤에는 C와 E에 A.cpp를 제출하며 어그로 엔딩을 완성했다.

 

아쉬웠던 점

 

• J에서 거하게 말아먹었다 ㅋㅋㅋ 처음엔 스코어보드 때문에 긴박했다고 해도, 이메이미가 중간중간 맞는 이야기를 했는데도 관찰을 못 버린 건 명백하게 잘못이다.
• C가 생각보다 쉬운 문제였고, 실제로 즈홒이 대회 끝나고 읽더니 뚝딱 풀었다. 스코어보드를 보고 풀이를 과신하는 실책과 (J) 그냥 쫄아버린 (C) 실책을 동시에 범한 셈이다.
• 즈홒의 D 풀이를 좀 더 같이 신경써줬어야 했다. 정해가 꽤 간단했기 때문에 시간을 조금만 더 투자했으면 맞는 풀이가 나왔을 것 같다.

사실 3~4등 정도의 팀은 스코어보드에 영향을 받기보다는 영향을 주는 팀이어야 하는 것 같다. 이 팀이 유지될런지는 모르겠지만 다음 기회가 있다면 좀 더 마이웨이를 하는 것으로. 끝!