220712 팀 연습 (CERC 2019)

셋은 CERC 2019를 사용하였으며, 팀원 간 거리가 멀어 아쉽게도 연습은 3컴 체제로 진행하였다.

 

내가 뒤, slah007 선배가 가운데, qjatn0120 선배가 앞을 보고 시작했다.

 

~0:19

나는 I, qjatn0120 선배는 A, slah007 선배는 F를 잡고 시작했다. F의 AC가 13분에 먼저 나왔으며, 나는 할만해 보였던 I를 계속 잡아 19분에 AC를 띄웠다.

 

~0:30

이후 qjan0120 선배의 A AC가 나왔다. 나는 J를 잡았으며, slah007 선배는 E를 잡은 것 같다.

 

~0:41

J를 다 짜서 냈더니 틀렸다. 바로 반례가 있음을 깨닫고 성의 없는 커팅을 해서 냈는데 바로 맞았다. 정확한 이유는 몰랐지만 어쨌든 기분이 좋았다. 대회 끝나고 솔루션을 찾아보니 대충 제곱근 분할법의 원리로 시간 복잡도가 보장되는 것 같다. 신기했다. 이후 K와 L을 봤는데, K는 풀지 말라고 지문에서 온몸으로 말하고 있어서 L로 넘어갔다.

 

~0:44

이후 C와 E의 AC가 나왔다. 나는 더러운 Case Work 문제인 L과 씨름할 준비를 했다.

 

~0:57

빠른 시간 내에 slah007 선배가 H를 맞아오셨다. 나는 세그트리를 여러 번 바꾸면서 L과 사투하고 있었고, qjatn0120 선배는 인터랙티브인 D에 도전하고 있었다.

 

~1:12

이후 D의 AC가 나왔다. 여기부터는 slah007 선배는 B, qjatn0120 선배는 H, 나는 L을 잡고 각자 도장깨기를 했다.

 

~2:43

qjatn0120 선배가 전문분야인 H를 맞아오셨다. D5던데... 확실히 아호코라식에 대한 이해도가 깊은 것 같다고 생각했다.

 

~4:07

이후 slah007 선배는 3시간 가량 로그를 하나씩 떼 가면서 B에 도전하시다 결국 맞아오셨다. 이것도 얘기를 들어보니 굉장히 어려운 문제 같았다.

 

문제별 요약

A (P4, solved by qjatn0120) : Manacher 기본 문제라고 한다.

B (D5, solved by slah007) : 대충 봤는데 어려워 보였다.

C (S2, solved by qjatn0120) : 문제를 읽지 않았다.

D (P3, solved by qjatn0120) : 문제를 읽지 않았다.

E (P4, solved by slah007) : 문제를 읽지 않았다.

F (G4, solved by slah007) : 문제를 읽지 않았다.

G (G4, solved by slah007) :문제를 읽지 않았다.

H (D5, solved by qjatn0120) : 주어진 조건을 아호코라식으로 분해한 후 선형 점화식을 만들어 행렬 곱셈을 하면 된다고 한다. 업솔빙 예정

I (P5, solved by leo020630) : 주어진 상황을 그래프로 나타낸 후, 길이가 작은 사이클부터 써주는 것이 최적이다. 나는 구현을 좀 무식하게 했다.

J (P2, solved by leo020630) : \(M\)이 \(\sqrt{N}\)보다 작은 경우 모든 정점 쌍을 비교해주면 되고, 큰 경우 각 정점에 연결된 간선을 확인하면 시간 복잡도가 보장된다. 구현은 Union Find로 한 후, 변화한 정점들만 롤백해주면 된다.

K (?, Not solved) : 멋지다

L (P3, solved by leo020630) : 케이스를 모두 써본 후, 열심히 구현하면 된다. 132나 213 등의 형태가 좀 어려운데, 약간의 그리디 아이디어를 얹은 후 세그트리를 지지고 볶으면 해결할 수 있다.

 

느낀 점

나름 매운 셋을 가져왔는데 팀원들이 잘 해줘서 놀랐다. 나름 전문분야들을 잘 잡은 결과라고 생각한다. 나는 나 나름대로 싫어하던 Case Work 문제들을 잡았는데 크게 무리 없이 풀어서 괜찮았던 것 같다.