2019 UCPC 예선 후기

프리즈된 스코어보드.

문제 - https://www.acmicpc.net/category/detail/2053

최종 스코어보드 - https://ucpc.acmicpc.net/contest/spotboard/449

 

I HATE PS★팀으로 UCPC예선에 참가해 38등으로 본선진출에 성공했다!

대충 우리 팀이 뭘 했는지 30분 간격으로 기억나는대로 적어보겠다.

0-30분:

A 9분 AC - gyuni가 시작하면서 읽고 바로 풀어냈다.

B 18분 AC - 내가 읽고 바로 풀었다. 밀면서 좌표가 어떻게 매핑되는지 헷갈려서 살짝 헤맸지만.. 종이에 정리를 잘 하고 풀자!

 

그 후 E, F, C번 정도를 읽어봤는데 잘 모르겠어서 넘겼다.

 

30-60분:

gyuni가 나한데 D번이 풀만한거 같다며 넘겨줬고, 나는 다소 해메다가 [해석할려는 string의 길이 300 이하의 substring]이 사전의 단어의 prefix로 몇 번 나타나는지 빠르게 셀 수 있으면 dp로 전환되는 문제임을 발견했다. 그 후 아호코라식/KMP쪽으로 생각해보다가 결국 사전단어의 prefix를 해싱해서 hash table에 집어넣는 식으로 세보고자 했다. 그 바로 전에는 prefix를 그대로 hash table에 넣는 식으로 구현하다가 10분쯤 구현하고 나서야 시간 내로 절대 안된다는 걸 깨닫고 해싱으로 고쳐서 구현을 시작했다.

 

60-90분:

I 65분 AC - 내가 2차원 배열로 전환해서 전탐을 하는 풀이를 발견했고, D번에 집중하기 위해 nevivurn에게 풀이와 함께 넘겨줬고 nevivurn이 잘 짜줘서 AC. 3차원 배열로 전환하는 더 깔끔한 풀이가 있지만 2차원 배열로 전환하는 건 문제를 풀기에 충분히 간단했다.

F 72분 AC - gyuni가 조용히 AC를 받아왔다. 난 처음에 보고 이런 미적분인가.. 싶고 그런 건 도저히 자신이 없어서 팀명의 유래를 생각해보자 일단 던졌는데 state representation을 정석대로 하면 나오는 깔끔한 dp풀이가 있었다.

나는 이 때 해싱코드를 짜본 게 꽤 오래되서 가물가물한 기억을 되짚어가며 D번의 해싱 코드를 짜고 디버깅하고 있었다. 아마 이때쯤에 누군가 나한테 "D번 풀리고 있냐"라고 물어봤고, 나는 "사소한 구현 문제가 있다. 10분 내로 풀린다"라고 답변했다.

 

90-120분:

J 94분 AC - nevivurn도 조용히 AC를 하나 받아왔다. 답은 반드시 어느 두 점을 잇는 최단거리 직선 위에 존재해야 한다는 관찰을 통해 풀어냈다고 한다. (귀류법 쪽으로 생각해보면 어렵지 않게 증명할 수 있다).

이때 나는 D번 해싱 풀이를 완성했으나 메모리 초과+런타임 에러 콤보를 맞고 정신을 못차리고 있었다. 다시 생각해 보면 prefix가 최대 10^6개 있는데, 이 prefix들의 hash값을 모조리 hash table에 넣어서 나오는 10^6개의 entry때문에 메모리 초과가 나는 듯 하다. 단순히 엔트리가 10^6개라고 생각해서 메모리 이슈는 없을 것이라 생각했는데, 해시 테이블에서 오는 오버헤드가 상당히 큰 듯 하다. (대회가 끝나고 로컬에서 랜덤맥스테케를 돌려봤는데 메모리를 4GB먹으면서 컴퓨터가 잠시 먹통이 되었다..ㄸ)

옆에서는 gyuni가 조용히 G번에 도전하고 있었고, 나와 nevivurn도 H번에 대해 시뮬레이션+메모이제이션이라는 결론에 도달해 nevivurn이 코드를 잡고 있었다. G번은 수학적인 접근이 까다로웠고, H번은 구현이 어려워서 결국 대회 끝까지 풀어내진 못했다.

 

120분-150분:

이 때가 대회 도중에 가장 무서웠고 심적으로 힘들었다. 내가 1시간 넘게 투자한 D번의 해싱 풀이가 어쩌면 메모리 제한이나 시간 제한에 들어가기 힘들 것이라는 사실이 조금씩 와닿았고, 프리즈된 스코어보드를 봤을 때 도저히 낮지 않은 페널티의 5솔로는 본선에 진출할 수 없을 것 같았다. 그럼 새로운 풀이를 생각해내야 하는데 문제를 다시 읽을 때 빨리 풀어내야한다는 압박감 때문에 도저히 문제가 제대로 읽어지지 않았다.

 

결국 나는 gyuni한테 도움을 요청했다. 나는 내 풀이를 gyuni한테 간단하게 설명하고서 다른 풀이가 있을지 같이 생각해달라고 했고, gyuni는 잠시 생각하더니 "이거 트라이 아니야?"라고 알려줬다. 메모리 제한 안에 확실하게 들어가면서 필요한 substring의 출현 횟수를 O(1)에 셀 수 있는 자료구조.. 를 지금까지 hash table로 만들려고 한 것이고, 트라이를 듣자마자 해싱을 트라이로 교체하면 맞을 수 있다는 확신이 들었다. 왜 이걸 생각을 못했지? 스트링 쪽 문제 연습이 심하게 부족한 듯 하다.. 이때부터 바로 트라이 구현에 들어갔다.

 

150분-190분:

구현에는 크게 두가지 실수를 해서 이것들 잡는 데에만 10분+1WA 를 썼다. 첫째로는 substring의 개수를 세는 도중에 정확히 어떤 substring을 골라서 trie를 따라가야 중복 카운트 없이 substring출현횟수를 셀 수 있을지 (나이브하게 모든 필요한 substring을 독립적으로 trie에서 따라가면 시간초과가 난다) 를 헷갈렸고, 트라이를 따라가며 prefix 개수만 세야할 때 트라이 노드를 새로 allocate해서 런타임 에러가 나는 코드도 한번 짜냈다. 이런 잔실수는 언제 안할수 있을까.. 여하튼, 이것들을 고치고 나서..

D 170분 AC! 들인 시간에 비하면 초라한 1.3KB짜리 소스로 결국 AC를 받아냈다.

이후 시간이 20분 남아서 G/H번 중에 하나를 도와줄려 했는데, H번은 구현을 끝내기엔 너무 많이 남아서 G번을 도와주다가 발견하지 못한 케이스를 하나 더 찾아내고 이걸 구현하려는 찰나 대회가 끝났다. (물론 이때 이미 서버가 터져있어서 제출은 못했겠지만..)

 

 

후기

내가 너무 내 실력에 대해 과다평가하고 있다는 것을 깨달았다. J나 F는 꽤나 전형적인 dp/관찰형 문제임에도 불구하고 아무런 아이디어가 없었고, 팀원들 덕분에 다행히 팀으로서는 풀어냈다. D번에서 밑도끝도 없이 말린 건 근본적으로 문자열 알고리즘에 대한 이해도 부족이였다. gyuni가 트라이를 알려주기 전까지는 단 한 순간도 트라이를 떠올리지 못했다. 해싱이 메모리/시간 제한 안에 대충 들어올 거 같았지만 보장은 없었고, 더 좋은 알고리즘이 떠오르지 않았기 때문에 구현에 들어갈 수 밖에 없었다. 그 외에도 위에 쓴/쓰지 않은 잔실수가 정말 많이 나왔는데, 이런 것들 때문에 풀이에 집중할 수 있는 시간이 더 줄어들어서 시간에 쫓겨가며 D를 풀었던 거 같다. PS를 잘 하고 싶다면, 내가 갈 길이 정말, 정말 먼 거 같다..

 

스코어보드 공개 후 후기 +

결과적으로는, 사실 낮지 않은 페널티의 5솔도 45등 이내에 들어 본선을 확정지을 수 있었다. D를 풀었음에도 불구하고 순위가 한 계단 내려갔고, 반면에 D를 풀지 않았어도 44등으로 대회를 마무리 지었을 것이다. 프리즈 전 5솔팀에 우리 팀을 제외하고 15팀이 있었는데 그 중 11팀이 한 문제 이상을 맞춰서 모두 우리 팀보다 더 높은 순위를 가져갔고(D에서 4틀을 해서 우리 팀의 페널티가 꽤 높아서 그런 듯 하다) 반면 프리즈 전 4솔팀은 상대적으로 문제를 풀어낸 비율이 낮았다. 흐음..