ACM-ICPC 2020 Seoul Regional 후기

2020. 11. 15. 00:36알고리즘 문풀/Others

작년보다 한 계단 오른 3위로 대회를 마무리했다.

ICPC를 마무리하면서 2020의 PS 일정은 사실상 마무리되었다. 11/12 solve 3등으로 전체 대회를 마무리했다.

굉장히 좋은 성적을 거뒀지만, 제 역할을 못한 것 같아서 많이 아쉽다. 기대한 것도 있었고...

 


대회 준비

팀 구성은 작년과 같이 imeimi / jhhope1 / TAMREF로 구성된 3인팀이었다. 사실 예선 때까지만 해도 거의 기대를 하지 않았다. 학기 일정을 소화하기에도 많이 벅찼고 PS를 거의 손도 대지 않았다. 그런데 솔직히 팀원이 imeimi인데ㅋㅋㅋㅋ 월파 욕심이 안 나기 어렵다. 폼이 많이 떨어진 상태에서 예선을 봤는데 생각보다 가능성이 보여서(??) jhhope1이 실력을 좀 키우자는 이야기를 했다. 결국 내가 아는 문제들을 즈홒한테 던져주고, 즈홒은 풀이를 짜고, 나는 그 풀이를 받아서 구현하는 Ternion식 훈련을 시작했다.

그런데 이 블로그를 보면 알 수 있듯이 성과가 엄청났다. 즈홒이 풀이 뽑는 걸 잘하는 걸 알고는 있었지만, solved.ac 기준으로 다이아랑 루비를 막 던지는데 엄청 잘 풀더라 ㅋㅋㅋㅋ 대회 이틀 전에 2018 대전에서 가장 어려운 문제 중 하나였던 Square Root를 풀었을 때는 자신감이 최고조에 달해 있던 상태였다.

반면 나는 여전히 팀에서 가장 위험요소가 많은 팀원이었다. 코딩을 많이 해야 하는 역할인데, 가끔씩 회복되지 않는 실수를 하는 문제가 몇 개 있었다. 코딩을 하는데 자꾸 로컬에서 몇 번씩 틀리고, 웰노운 자료구조를 구현하는 데 기초적인 실수를 하고, 또 기억을 못하고... 멘탈의 문제라고 보기도 어려웠던 게 SCPC나 ICPC 예선에서도 실수가 나고, 편하게 백준 풀 때도 실수가 났다.  결국 실력이 떨어졌단 걸 알고 있고, 문제를 많이 풀면서 실력을 끌어올려야 한다는 걸 알고 있었음에도 연습할 시간을 많이 만들지 못해서 불안했다. 그래서 맨날 "이번에도 4등하면 내 탓"이라고 말하고 다녔다... 그 시간에 연습이나 할걸.

아무튼 대회날이 왔다. 안하던 팀연습도 두어 번 하고, 팀 전략 개편도 이야기를 해봤다. 다만 아직 즈홒의 코딩이 안정적이지는 않은 상태라 작년 그대로 에이스 imeimi / 코딩머신 TAMREF / 풀이뽑기 jhhope1의 전략을 유지하기로 했다.

 

초반 (~60분)

사전에 계획한 대로 내가 템플릿을 따라 치고, 인쇄가 되는 순서대로 문제들을 가져가기로 했다. 항상 초반에 이상한 문제 잡고 뇌절하는 버릇 때문에 이번에는 "진짜 쉬운 문제"를 빠르게 찾는 데 주력하기로 했다.

이메이미가 A, 즈홒이 B를 가져갔고 이메이미는 바로 "지금 풀 문제는 아니다"며 A를 버리고 C로 갔다. 템플릿을 다 치니까 즈홒이 B 문제지를 짜라고 가져다주더라. 지문에서 "이긴다"가 greater인지 geq인지 안보여서 살짝 고민했는데, 그런 고민은 일단 타이핑하면서 하기로 했다. 예제 3개가 다 나오길래 그냥 냈고 맞았다. (6min)

그 사이 이메이미가 C를 밀 수 있다며 코딩을 스왑했다. 나는 남은 문제 중에 제일 위에 있는 E를 봤고, 쓱 보니 빨리 풀리겠다 싶어서 대강 설명해주고 즈홒한테 넘겼다. D를 잠깐 봤는데 KOI 주유소인가? 했지만 풀이가 쉽게 나오지 않았다. 그사이 이메이미는 C를 빠른 속도로 AC. (16min)

나는 지문이 망한 F와 기하처럼 생긴 H를 보며 고통받고 있었다. 그 사이 즈홒이 E 풀이를 만들어서 후다닥 짰는데 틀렸다 ㅋㅋ;; 그래도 그 사이 이메이미가 G 풀이를 만들어서 맞았다. (31min) 풀이가 복잡할 수도 있었지만 즈홒의 아이디어가 괜찮았다는듯. 

그 사이 즈홒이 풀이에서 빠진 부분을 찾아서 메꿨다. 예제도 하나 만들어서 테스트한 뒤 든든하게 AC. (35min) 아마 이 때 2등이었고, 20등 근처에서 놀던 작년에 비해서 운영이 꽤 괜찮아졌다는 느낌이 들었다. 이때까지만 해도 월파가 눈에 아른거렸지..

순서가 어땠는지는 기억이 나지 않는데, 컴퓨터 앞에 앉아있던 이메이미한테 내가 J 풀이를 던졌다. 그냥 가우스 소거법을 하면 되는 문제였는데 출력이 많이 이상했나보다. 약간 괴로워하더니 쓱쓱 밀면서 AC. (44min)

그 뒤로 새로운 풀이가 나오지 않아서 코딩큐에 남아있던 A를 잡았다. 그 와중에 고대팀에서 H를 풀었다는 제보가 나와서 후다닥 달려갔다. 일단 기하가 아니라는 얘기니까. 작년에 스코어보드에 영향을 받기보다는 주네 어쩌네 말하던거 하나도 못지켰다...

 

중반 (~180분)

역시 이멘은 이멘답게 A를 첫줄에 맞았다. 구현이 엄청 더러웠던 것 같은데ㅋㅋ 이멘한텐 어림도 없다. (78min) 그 사이에 H가 그냥 FFT문제라는 결론이 나왔고 바로 12분동안 팀노트를 열심히 베껴서 맞았다. (90min) J, H 둘다 팀노트 테스트용 수학문제인데.. 한국에서 이런 문제가 나오는 게 신기하긴 했지만 퀄리티가 그다지 높지 않아서 좀 실망스러웠던 면이 있다.

7솔을 하고 보니까 남은 게 D, F, I, K, L이었다. 이중에서 I와 L을 봤는데 I는 3D 쿼리같은게 필요해보여서 기분이 나빴다... 만약에 이 문제를 처음 본 게 이메이미였으면 그냥 밀었을 것 같은데 ㅋㅋ 경험이 부족했던 탓인 것 같다. 애초에 200만 2D query같은 게 말이 안 된다고 생각해서 다른 풀이를 좀 생각하다가 그냥 버렸다.

L은 어디서 보던 식 하나만 덜렁 던져져 있었는데, '19 snupc 꽃집이랑 비슷한 것 같아서 monotone queue opt인 거 아닐까? 하는 생각과 동시에 뇌절을 시작했다. 근데 이걸 짜 봤어야 알지 ㅋㅋ

F는 지문이 너무 이상해서 이해를 포기했고, D는 시도해본 몇 개 풀이가 잘 안 돼서 교착 상태에 빠졌다. 그 상황에서 즈홒이 K를 보고 낄낄대더니 풀이를 가져왔다. 입출력 형식 보고 한숨만 푹푹 쉬다가 풀이를 듣고 구현에 들어갔는데, 그러지 말았어야 했다.... 풀이를 좀 더 스스로 검토해볼걸.

어차피 다른 문제 풀이도 없는데 코스트 큰 구현을 해도 괜찮겠지 싶어서 컴을 잡았는데 미리 충분히 생각하지 못한 부분이 꽤 많았다. 고통받으면서 완성한 첫 코드는 대충 220줄 정도였고, 힘차게 터져나가는 코드를 여기저기 때웠지만 RTE를 받았던가 그랬다. 이때부터 분위기가 좀 나빠진 게 느껴졌다.  틀리고 나서 코드를 프린트했는데 A4로 5장이 나오더라 ㅋㅋ

 

후반 (~300분)

이때부터는 이메이미의 원맨쇼였다.내가 뇌절을 하는 사이에 꽤 많은 문제의 풀이가 나온 모양이었다. 우선 "이거 되지 않을까?" 하는 F를 슥슥 짜더니 맞아버렸다. (196min) 그 사이에 내가 K를 풀다가 틀리고, 다시 이메이미가 들어가서 풀고, 내가 들어가서 고치다 틀리고... 하던 기억밖에 없다.그 사이 즈홒이 L의 돌파구를 찼는 관찰을 해냈고, 이메이미가 dnc opt의 성질을 관찰해서 맞았다. (218min) 내가 뻘소리만 안했어도 더 빨리 맞았을 문제들이었다. 반대로 I는 무슨 뻘소리라도 했어야 더 빨리 맞았을 문제였다 ㅋㅋㅋ 물론 결과론이지만...금방 풀릴 줄 알았던 K가 계속 레드카펫을 깔았고, 심적 압박감이 너무 커졌다. 그 사이에 풀이에 심각한 지장을 주는 반례를 찾았다. 시간이 3시간 더 있었다면 밀고 짰겠지만 당연히 그럴 시간은 없었고, 고칠 수 있다고 믿고도 있었다. 물론 돌아오는 결과들은 전부 붉었다.그 사이에 이메이미는 D, I 풀이를 다 가져와서 하나씩 요리를 했다. 물론 꽁으로 푼 건 아니고, D를 풀때는 좀 고생했던 것 같다. 다익스트라가 생겼다가 사라졌다가 하더라. 와중에 나는중간에 K를 고쳤답시고 컴퓨터를 뺏었다가 한 번 더 틀렸다(...) 그 이후로는 이메이미가 D, I중 하나를 풀기 전까지는 간섭하지 않기로 했다. 결국 D를 먼저 AC. (265min)이제 결과가 어떻게 되었든 K는 맞아야 하는 상황이었다. 하지만 코드를 고쳐도 고쳐도 틀린 부분이 보였고, 확률은 떨어져갔다. 이메이미의 구현력을 믿고 K를 몇 번 더 시도했지만 어림도 없었다. 결국 컴퓨터를 넘겼고, 이메이미는 역시 에이스였다. I AC. (281min)병적인 예제를 4개 정도 만들어서 테스트를 해봤고, 반례를 찾았다. 이걸 고칠 때까지만 해도 정말 맞을 줄 알았다. 하지만 290분에 제출했을 때도 WA를 받았다.생각한 모든 로직이 맞고, 떠올린 모든 테케를 통과하는데 결과는 틀렸다. 자꾸 시계에 눈이 갔다. 결국 의미 없는 짓을 몇 번 더 하다가 그대로 대회가 끝났다.

 

후기

K 언급을 대체 몇 번 한 거야 ㅋㅋㅋㅋㅋ

작년에는 4등을 해도 즐거웠는데, 올해는 욕심인지 기대감인지 모르겠지만 3등을 하고도 기분이 썩 개운치 않다.

수정한 전략이 잘 먹혀서 초반에는 순항했지만, 결정적인 순간에 내가 I, K, L에서 나쁜 버릇들이 나오며 페이스를 떨어뜨린 게 아쉬운 결과로 이어진 것 같다. 경험이 부족한 티도 많이 났고..

이메이미는 2인분 이상을 해줬고, 즈홒도 충분히 자기 역할을 다해준 것 같다. 결국 "4등하면 내탓"어쩌구 하던 말이 현실이 됐다 ㅋㅋ

아마 내년에는 셋 중 하나는 병역을 해결하러 갈 것 같아서 팀이 유지될지는 모르겠다. 유지되지 않아도 할말은 없고...

팀원들에게 너무 고맙고, 좋은 결과를 거둔 주변 사람들에게 축하의 말을 전한다. 로터스 월파축하해 ㅋㅋ

 

'알고리즘 문풀 > Others' 카테고리의 다른 글

제 3회 IDTCup 개최 후기  (0) 2021.05.10
UCPC 2020 본선 후기  (0) 2020.08.01
ICPC Seoul Regional 2019 후기  (1) 2019.11.13
IOI 2014 Holiday  (0) 2019.08.29
[PS 켠왕 #1] BOJ 10641 The J-th Number  (0) 2019.08.15