220401 팀 연습 (BAPC 2018p)

분명히 작년에 ICPC를 같이 나갔지만 놀랍게도 처음인 팀 연습이다. slah007, qjatn0120 선배와 함께 진행하였다.

셋은 BAPC 2018 예선을 사용하였다. 

 

~00:00

동아리 부원들의 실력 증진 차원에서 팀 연습을 함께 진행하였는데, 여러가지 issue로 인해 예정보다 10분 늦게 시작하였다. 내가 A~D, qjatn0120 선배가 E~G, slah007 선배가 F~K를 잡기로 했다.

 

00:10

A가 좀 화나게 생기긴 했지만 문제 자체는 간단하다는 것을 깨닫고 바로 짜 AC를 받았다. 5분 후에 H 역시 AC가 나왔다.

 

00:26

영어 지문을 읽는 데에 조금의 애로사항이 있었지만, 다 읽고 나니 B도 쉬웠다. 쉽게 짜서 AC를 받았고, 거의 동시에 E도 AC가 나왔다.

 

00:39

J AC가 나왔다. 문제는 읽어보지는 않았지만 전형적인 MST 문제라고 한다.

 

00:52

나는 B를 푼 후 C를 열었지만 풀이가 바로 보이지 않았고, 조금 생각한 후 D를 보았다. D는 대충 각 지점에서의 차이 값이 Convex할 것 같았고, 시간제한이 5초였기 때문에 무지성으로 삼분탐색+펜윅을 짰다. 한번 틀렸지만, 최소값을 가지는 지점이 지나치게 길 수 있어서 그 부분을 이분탐색으로 처리해준 후 AC.

 

01:05

C를 좀 보다보니 풀이가 나왔다. 가능한 쌍 중 가장 작은 M개를 모두 뽑고, 뽑힌 M개의 길이를 정렬한 것이 케이블을 정렬한 것과 1대1로 대응시켰을 때 모두 작아야만 한다. M개를 뽑는 것은 우선순위 큐로 적절히 처리할 수 있다. 한번 틀리고 코딩 미스를 수정해준 후 AC. 01:04에 G또한 AC가 나왔다.

 

~01:52

나는 배정된 4문제를 모두 풀었고, qjatn0120 선배 역시 레전드 기하 문제였던 F를 제외하면 2문제를 모두 풀어서 slah007 선배를 도우러 갔다. 뒤의 4문제중 남은 것은 I와 K였는데, I를 slah007 선배가 계속 잡고 있었기에 나와 qjatn0120 선배는 K를 보았다. K의 범위가 상당히 작아 \(O(100B)\) 정도에 돌아가는 냅색을 짜면 될 것 같았고, 각자 짜기로 한 후 qjatn0120 선배가 01:52에 AC를 받았다. I 역시 slah007 선배가 01:40 정도에 AC를 띄우셨다. 이 과정에서 \(O(NlgN)\) Suffix Array가 필요하다고 하셔서 드렸는데, 팀원들과의 코딩 스타일이 상당히 맞지 않는다는 것을 느꼈다. 주의해야겠다.

 

~03:00

이후 선배 두분은 레전드 기하 문제인 F를 푸셨고, 나는 K를 업솔빙했는데 계속 틀렸다. 알고보니 문제를 잘못 읽은 거더라. F는 결국 풀리지 않았고, 그렇게 10/11 솔으로 연습을 마무리했다.