SWERC 2020 팀연습 후기

기존에 두 번의 팀연습이 더 있었지만 블로그 후기를 쓰는 게 생각보다 시간을 많이 잡아먹어서 팀원이 대신 글을 작성했다.

5월 31일 1학기 마지막 팀연습을 진행했고 남은 기간에는 ICPC 기출을 여러번 풀 것 같다.

방학때는 주말에나 연습이 가능할 듯 싶다.

팀연습 타임라인

SWERC2020으로 정해졌고. 14:05분 부터 5시간짜리 문제를 풀었다. 나는 코딩은 저번 부터 그냥 안하고 해석과 풀이 내는데에만 집중을 했다.

14:07 E Solve

내가 A번을 읽기 시작했고, dtc03012님이 B번을 읽었고, Lemonade255는 실행시간이 짧은 문제가 쉬운 문제라면서 E를 읽었다. E는 브론즈 문제라면서 빠르게 코딩을 끝내고 바로 맞추었다.

끝나고 읽어보니 $min(\frac y x)$ 를 출력하면 답이다.

14:17 A Solve

A도 읽어보니 쉬웠다. $3N$개의 문장을 많이 나온 순서(같으면 나중에 나온 순서)대로 정렬하면 되는 문제이다. Lemonade255한테 설명하고 풀게 시켰다. std::map 같은걸 사용하면 쉽게 풀릴거라 생각했는데 약간 코딩 헤매긴 했지만 한번에 풀었다.

14:31 C Solve

나랑 dtc03012님이 A번 코딩하는 동안 B번이 답이 없다는걸 읽어보고 깨닫고 C번을 읽었다. 근데 C번도 쉬웠다. 이분탐색 -> 이어져서 가로 세로 막는지 판별 -> disjoint set 사용하면 쉬움 이렇게 풀이가 나오는데 1~2분도 안 걸린 것 같다. A번 코딩 끝나고 바로 코딩해서 AC

15:50 K Solve

K번은 A코딩을 끝내고 Lemonade255가 바로 읽고 Rabin-Karp로 짜면 된다고 얘기를 했다. C를 코딩할때 쯤 아이디어가 나왔으나 코딩이 매우 오래 걸렸다. 라빈카프 Hash 하는 것 자체가 충돌날 확률이 너무 높아서 그걸 해결하는데 고민을 많이했다. Chinese Remainder Theorem 같은걸 쓰려 했으나 결국에는 __int128로 코딩을 해서 제출해서 맞추었다.

그 사이에 F번을 고민하고 있었는데 F번이 되게 풀이가 나올듯 말듯 안나왔다. F번은 좌우 개념이 없는 이진 트리를 $1$~$N$번 노드를 이용해 만드는데 부모 노드는 항상 자식 노드보다 번호가 클 때 $R$을 리프 노드로 하는 트리 개수가 몇 개인지 묻는 문제였다.

$N$부터 $R$까지는 그냥 배치하고 $R-1$부터 $1$번까지를 어떻게 배치할까 이런식으로 고민하고 그냥 배치하는건 카탈란수 인가? 이런 여러가지 생각을 하고 있었다. 일단 트리 dp긴한데 식을 정확히 어떻게 짜야할지 고민하는데 어려워서 계속 잘 안 나왔다.

15:57 D Solve

K 고민하고 있는사이에 D번 푼 사람이 더 많아졌길래 D번을 읽었는데 너무 쉬워서 문제를 잘못 읽은줄 알았다. 그냥 다익스트라 돌려서 갈수 있는 간선의 개수를 세는 문제이다. dtc03012님한테 풀이 확인 받고 코딩해서 바로 맞추었다.

16:38 F Solve

다같이 F를 고민했는데 dp식을 알 것 같다면서 Lemonade255가 알아서 뚝딱 풀어버렸다. 아직 이 문제는 나는 풀이를 정확히 모른다.

이때까지 한 번도 WA 없이 모든 문제를 원샷 원킬로 맞춰서 페널티가 상당히 잘 관리되었다.

16:49 I WA

I번은 재미있는 문제였다. 무향 그래프에서 최단 거리가 2인 곳에 간선이 생기는 작업을 반복할 때 몇번만에 완전 그래프가 되는지 묻는 문제다. 처음에는 몇번 해보니깐 그래프의 지름(모든 정점 쌍의 최단 거리 중 max 값)을 $D$라고 할 때 $ceil(\log D)$만에 된다는 것은 증명을 했다.

그러나 $D$를 시간내에 구하는 방법을 알 수가 없어서 고민이었는데 트리의 지름 구하듯이 DFS를 한번 돌리고 다시 DFS로 가장 먼 거리를 측정하는 방식을 하는데, 그래프의 경우 어떤 정점을 선택하냐에 따라 제대로 못 구할 수 있기 때문에 random 하게 돌려가면서 하는 방식을 했다. 결과는 WA여서 다른 결정론적이 풀이 방법이 있을지 계속 고민했다.

18:12 H Solve(+2) I WA(+3) B TLE

H번은 처음에 이걸 어떻게 세그먼트트리로 풀지 했는데 dtc03012님이 보고서는 PST문제라고 했다. 그러고 보니 완벽히 PST 기초 문제라는 것을 알 수 있었다. 그러나 우리의 문제는 PST를 짜는 것을 할 수 없었고 팀 노트가 있다 가정해서 과거의 PST 코드를 가져왔다. 그 과정에서 다른 컴퓨터(코딩 자체는 1개로 했으나 문제 보는용)로 전달하려고 B번 문제를 이용해 전달했다.

I번은 반복 횟수를 바꿔가면서 했지만 계속 WA가 나왔다.

H번은 2번 틀렸지만 PST 템플릿을 바꿔서 새로 짜니깐 바로 맞았다.

18:42 I Solve(+7)

I 번을 반복 횟수를 바꿔가면서 어떻게 잘 비비니깐 놀랍게도 통과를 했다. 랜덤 풀이가 맞긴 해던 것이다. 이 문제는 끝나고 랜덤이 정해인지 확인하려고 풀이를 봤는데 DFS를 한번만 돌리고 풀이를 할 수 있는 방법이 있었다. 보고 좀 소름이 돋았는데 확인하려면 영상 참조. 재밌는 문제였다.

19:05 종료

마지막으로 L번과 G번을 보고 있었다. 문제 해석 같은걸 끝내니깐 10분정도 밖에 남지 않았다. 그래도 L번의 풀이는 꽤 정답에 가깝게 간거 같은데 시간이 부족했다. G번은 정해에 가깝지 않게 가고 있었는데 G번도 1시간 정도면 우리 팀의 실력이라면 충분히 풀만한 문제인 것으로 파악 됐다.

결과 및 후기

8 Solve 1114 페널티

B, J, M은 풀기 힘들것 같고 L G는 풀만한 문제였는데 시간이 부족했다. F, I, K에서 시간을 좀 줄일 수 있었는데 그쪽에서 시간을 많이 쓴것 같다. 특히 I번이 아쉬운데 I번도 너무 결정론적 풀이를 내려고 시간을 오래 고민했는데 일단 코딩 해보면서 하는게 나았을것 같다.

항상 그래도 초반 뇌절이 한 두문제는 있었는데 이번에는 없었던게 고무적인 것 같다. 코딩도 안정적이게 되었고 팀 합도 잘 맞는 것 같다. 꽤 괜찮은 실력이 나올 것 같지만 시간 배분이 가장 어려운 것 같다.

WF 나가려면 10솔브는 기본이고 11솔브할 느낌상 대학교 3학교는 있었을것 같아서 좀 더 실력 많이 올려야할 듯 싶다.