220601 팀 연습 (SWERC 2018)

셋은 SWERC 2018을 사용하였으며, slah007 선배와 둘이서 5시간동안 진행하였다. 추가로, DGIST의 SudaL 팀과 연락이 닿아 시간을 맞춰 진행하였다.

 

~0:11

slah007 선배가 앞쪽, 내가 뒤쪽을 보고 시작했으나 왜인지 A가 쉽다는 것을 내가 더 먼저 알아채 짜서 맞았다.

 

~0:19

slah007 선배가 E를 코딩하는 사이, B와 D가 풀 만 하다는 것을 깨닫고 풀이를 구상했다.

 

~0:25

E AC가 뜬 직후 B 코딩을 시작해 빠르게 맞았다. Parametric Search가 가능하다는 것과 문제에서 주어진 조건을 잘 이용하면 비교적 쉬운 방법으로 문제를 해결할 수 있다.

 

~0:45

D 풀이 또한 나온 상태였기에 B를 맞고 바로 코딩에 들어갔다. B보다 훨씬 많은 시간을 쓴 후 AC를 띄웠는데, 나중에 티어를 까보니 B가 더 높길래 조금 놀랐다.

 

~1:21

내가 B와 D를 코딩하는 사이 slah007 선배가 E의 풀이를 만들어 놓았다. 문제는 특정 문제들과 매우 유사한, 다익스트라와 세그트리를 섞어놓은 웰노운성 자료구조 문제이다.

 

~1:48

남은 문제들 중 제일 쉬워보인 K를 잡았다. 문제를 먼저 읽은 slah007 선배가 Z 알고리즘 등의 얘기를 하시길래 좀 쫄았는데, 대충 보니까 해싱 후에 \(O(N^3)\) DP를 돌리면 그냥 풀릴 것 같았다. 뚝딱 짜서 냈는데 틀리길래 문제를 다시 잘 보니까 문자열에 소문자, 대문자, 숫자가 다 포함될 수 있다더라. 이런거는 예제에 좀 넣어주면 안되나.. 라는 생각을 하며 고쳐서 바로 AC를 맞았다.

 

~2:41

사실 선배가 E를 코딩하는 동안 F의 풀이 또한 만들어 놓았다. 뭔가 뚝딱 푼 것 같지만 25051과 거의 유사한 세팅이었기에 풀이를 찾는 것은 어렵지 않았다. 게다가 DGIST 팀에 저 문제의 출제자가 계셔서 살짝 놀랐다. 내가 K를 짜는 동안 선배한테 문제와 풀이를 설명해드리고 K를 맞자마자 코딩을 바꿨는데, 뭔가 잘 안풀리시는 것 같았다. 하지만 바로 코딩에 들어갈 수 있는 문제가 없었기에 선배를 믿고 기다렸고, 1시간 쯤 지난 후에 AC를 받아오셨다.

 

~5:00

놀랍게도 이후 한 문제도 풀지 못했다. 셋 자체가 손을 대기가 거의 불가능한 문제 2개를 포함하고 있었고, 남은 두 문제를 열심히 시도했다. 하지만 한 문제는 풀이를 찾지 못했고, 그림부터 정말 읽기 싫게 생긴 I는 내가 가까스로 지문을 이해한 후 (사실 아니었다) 열심히 코딩했지만 맞왜틀에서 벗어나지 못했다. 결국 연습이 끝나기 직전 테케를 까보고 나서야 내가 지문을 잘못 이해했다는 것을 깨달았고, 연습이 끝난 후 1분만에 고쳐서 맞았다.

 

문제별 요약

A (B1, solved by leo020630) : 그냥 하라는 대로 구현하면 된다.

B (P5, solved by leo020630) : Parametric Search를 얹은 후, 각 행에서 구간이 하나임을 이용해 multiset 등으로 구간의 교집합의 크기를 관리해주면 된다. 

C (?, Not solved) : 최소 다이아 정도의 사전지식 같은데.. 모르겠다. 에디토리얼 말로는 Knuth의 저서에 있는 예제라고 한다.

D (G3, solved by leo020630) : 각 열에 대해 최소-최대 구간을 뽑아준 후, 잘 스위핑하면 된다. 구현 난이도는 B보다 어려웠지만, 풀이를 떠올리는 난이도가 B보다는 조금 낮은 것 같다.

E (G4, solved by slah007) : 뭔가 더러운 구현? 수학? 문제 같다.

F (P2, solved by slah007) : 각도 정렬+스위핑을 잘 짤 수 있다면 문제를 해결할 수 있다.

G (P1, Not solved) : 잘 모르겠다.. 재귀 진짜 못하는 것 같다.

H (P1, solved by slah007) : 문제 자체가 2472와 99% 유사할뿐더러, 저 문제를 풀어보지 않았더라도 2336의 풀이를 안다면 쉽게 풀이를 떠올릴 수 있는 것 같다.

I (P5, (up)solved by leo020630) : 그냥 더럽다. 그림부터 읽기 싫게 생겼는데, 이상하고 쓸데없는 요소들이 문제에 많아서 정말 거슬린다.

J (?, Not solved) : 이게 PS 문제가 맞을까?

K (P4, solved by leo020630) : 행렬 곱셈 순서와 비슷한 \(O(N^3)\) DP를 사용해 문제를 해결할 수 있는데, 문자열 비교를 \(O(1)\)에 해야 해서 해싱을 사용하였다.

 

느낀 점

사실 셋이 약간 마음에 들지 않았다. 프랑스산 지문인 것 같은데, 지문이 지나치게 예술적이어서 읽기가 힘들었다. 셋의 전체적인 컨셉 또한 우리나라 대회들의 느낌과는 살짝 맞지 않았던 것 같다.

 

비슷한 실력을 가진 팀과 함께 스코어보드를 띄워 놓고 하니 대회 느낌도 나고 자극도 더 되어서 좋았던 것 같다. 혹시 또 함께 하시고 싶은 팀 있으시면 연락주세요~

 

비교 대상이 있으니 우리 팀의 장단점을 조금 더 확실히 파악할 수 있었던 것 같다.

장점 : 골드 이하의 쉬운 문제를 찾는&푸는 속도가 비교적 빠르다. (허나 이는 UCPC나 ICPC 본선에서는 그닥 재미를 보지 못하는 장점이다.) 플래티넘 이하 문제들은 95% 이상의 확률으로 풀이를 찾는다. 잘하는 분야가 약간씩 다르다. 소통이 잘 된다..? 

 

단점 : 팀원마다 가리는 분야가 조금씩 있다. 중반~후반부에 어려운 (플레 상위권 이상) 문제를 풀 때 구현 미스가 나거나, 한 명이 이상한 짓을 하기 시작하면 단체로 말리는 것 같다. 씹덕력, 즉 웰-노운에 대한 대비가 다른 팀들에 비해 약하다 = 다이아 이상의 어려운 문제들의 풀이를 뽑아내는 데에 있어 상대적으로 경험이 부족하다.

 

아쉽게도 2명이서 진행하긴 했지만, 여러모로 유익했던 1학기 마지막 팀 연습이었다.

함께 해주신 SudaL 팀원들에게 감사를 표한다.