[UCPC 연습] UCPC 2019로 팀연습을 해보았다.

UCPC 2021이 이제 한달도 남지 않았다.

이번에 나는 군생활을 하면서 알고리즘 실력을 향상시키고 여러 대회를 경험해보고 싶었기 때문에

우리 학교 알고리즘 소그룹에서 팀원을 구해 경험삼아 대회에 나가볼 사람을 구했었다.

 

2018년, 2019년, 2020년에 비해 이번년도에는 건국대 팀이 많이 없었다. (UCPC 참여인원 중 건국대학교 소속인 사람은 우리 팀 포함 총 4명뿐이었다.)

 

속상하기도 했지만, 이왕 이렇게 된거 열심히 해보자 다짐하게 되는 계기가 됐다.

 

UCPC 본선 진출은 상위 50팀 내외이다. 이는, 아무리 못해도 최소 플레티넘 중위 문제를 해결해야 본선에 진출할 수 있다는 의미. (UCPC 2020은 서버가 터져서 거의 모든 팀을 본선으로 보내버린 예외의 경우) 

 

나는 이번 년도에 본선진출을 기대하기보단, 실전 경험 및 실력상승을 위해 참여에 의의를 두고 신청하였다.

전역하고 2022년, 또는 복학하고 학교생활하면서 2023년, 2024년, 2025년 중 한 해엔 반드시 본선에 진출하고 싶다.

---

UCPC 팀연습 3회 째:

UCPC2019 예선 문제셋을 해결해보았다.

https://www.acmicpc.net/category/detail/2053

UCPC 2019 예선

순서대로 풀면 난이도 예측이 가능할 듯하여 일부러 당시 문제순서 순으로 풀지 않고 순서를 섞었다.

solved 티어 보기 설정은 해제해두었고, 알고리즘 분류를 보지 않고 해결하도록 했다.

 

ucpc2019 스코어보드는 아래 링크에서 확인가능하다.

https://www.acmicpc.net/contest/scoreboard/449

UCPC 2019 온라인 예선 - 스코어보드

풀이집 pdf는 아래 링크에서 확인가능하다.

http://2019.ucpc.me/qualifier/

온라인 예선

 

당시 5솔이 커트라인이었고, 우리는 무려 4솔을 해냈다!

생각보다 팀원들이 되게 잘해주어서 너무 기뻤다.

물론 4솔과 5솔의 차이는 굉장히 크다.

그래도 한 문제 차이까지 나아갔다는 것에 꽤나 기뻤었던 기억이 난다.

 

당시 연습상황을 복기해보겠다.

---

• yunsuk0616님이 A~C번, 내가 D~F번, choisk0531가 G~J번을 쭉 살펴보았다.
• yunsuk0616님께서 A번은 보자마자 패스하셨고, B번도 조금 고민하시다가 패스하셨다 / D~F번을 살펴보던 나는 D번이 dp 또는 그리디일 것이라 예측. 그러나 딱히 방법이 생각나지 않아 패스하였다. E번은 dp, 조합론일 것이라 판단. 바로 시도해보았다. / choisk0531은 G~J를 쭉 살펴보고 J번 AC
• yunsuk0616님이 C번 AC / 중간쯤에 E번이 dp 점화식이 보이지 않자, 그림을 그려 5, 6, 7번째 항을 찾다가 좌표로 접근해보았고, 그래프 및 좌표평면으로 접근해보는 방법 생각. N이 작고 이미 갔던 길은 되돌아갈 수 없으므로 2^22=400만으로 백트래킹 또한 가능하겠다고 생각하였다. / choisk0531이 H번을 고민하던 중 곧 해결할 수 있을 듯하다고 함.
• yunsuk0616님이 D, F번 문제를 살펴보기 시작 / 난 E번에서 예제입력3이 자꾸 다른 답이 나와 코드 문제점을 계속 찾고 있었음 / choisk0531이 H번 AC.
• yunsuk0616님이 D번은 트리, F번은 트라이일 듯하다고 언급. 난 D번은 dp || greedy, F번은 dp라 판단하였기 때문에 의견이 달라 일단 패스하였다. / 한참 후에 틀린부분을 찾고 고쳐 E번 AC / choisk0531이 I번 시도하다가 N의 범위를 놓쳐 MLE 코드 제출. 
• 이후 B번 dp점화식이 대략 d[N][6][6][6]꼴임을 예상했으나, 기댓값의 의미가 애매하다 판단하여 여러 명이서 서로 토론하던 중 시간(3시간) 종료. I번은 공간복잡도가 O(N^2)이 아닌 풀이를 떠올리기 어려워 모두 머리맞대고 고민하다가 패스.

---

나중에 알고보니 F번은 yunsuk0616님 의견과 내 의견 모두 맞았다... 트라이 + dp 문제였다...

트라이도 약한데 dp까지 짬뽕돼있으니 굉장히 어렵게 느껴졌다.

 

앞으로 열심히 공부해야겠다.