2024 KAIST 14th ICPC Mock Competition 후기

셋: https://www.acmicpc.net/category/detail/4305 (https://www.acmicpc.net/contest/view/1380)

 

서론

 

"그 대회"에 다녀오고 처음 쓰는 블로그 글이다. 사실 진짜 다녀왔는지 아직도 잘 실감이 나지 않는다. 7일(특히 5시간)은 찰나처럼 짧았고 한 달은 억겁처럼 길게 느껴지니 생체시계가 망가진 것만 같다. 시간 순서대로라면 저것을 먼저 작성해야 하는 것이 맞으나, 규모로도 내용으로도 아직은 아무렇지 않게 다루기가 조금 힘들다. 하지만 결국 쓰긴 해야 하는 내용이라 빠르면 리저널 후, 느리면 방학에 시간을 두고 시작하게 될 것 같다. 그 사이에는 ICPC 등의 여러 이벤트도 있고 블로그를 방치해둘 순 없으니 밀린 내용들부터 포스팅하려고 한다.

 

AllSolvedin1557 팀의 여정은 끝났지만 사실 입대 예정인 petamingks를 제외한 나와 kwoncycle의 사이클은 그닥 달라진 것이 없다. 팀원이 slah007 선배로 바뀌었다는 것을 빼면 뭐 문제 풀고 대회 나가고.. 진짜 라스트 댄스를 위해 남은 1년은 별반 다르지 않게 지낼 예정이다. 말은 이렇게 했지만 한국 돌아와서는 온갖 의욕이 다 떨어진 상태였는데, 마침 귀국 2주 뒤 공휴일이라는 적절한 시점에 서울이 아닌 대전이라는 적절한 장소에서 적절한 퀄리티가 보장된 대회가 열린다는 소식을 들었다. 복귀의 시발점으로 아주 적절한 선택으로 보였고, 대회 망했다고 계속 쉬고만 있을 수는 없었기에 신청하였다.

 

팀명은 수많은 ICPC 팀명 후보 중 하나였던 Poking University로 정했다. 실제 팀명으로 쓰기에는 길이도 길고 뭔가 문제가 있을까봐 보류했는데 적절한 용도로 사용된 것 같아 기쁘다. 실제 리저널에서 사용할 팀명은 Pourist로, 비슷한 뉘앙스에 유관력을 조금 더 가미하였다. 이 대회는 Team Pourist의 첫 번째 팀 연습으로, 3코더 체제가 가능해졌기에 특별한 전략은 없이 알아서 잘 풀기로 했다.

 

대회 중

 

kwoncycle이 앞, 내가 가운데, slah007이 뒤를 보고 시작했다.

 

~0:24 (2솔브)

slah007이 F, kwoncycle이 B를 각각 짜서 맞았다. 내가 처음으로 본 문제는 E였는데, 그냥 MCMF를 돌려도 될지 의문이 들었지만 팀원들이 하라고 해서 + 컴퓨터가 비어서 일단 짜보기로 했다.

 

~0:54 (5솔브)

열심히 복붙한 MCMF 코드는 TLE를 뱉었다. 다행히 그 사이 다른 팀원들이 쉬운 문제들을 잘 풀어주었고, kwoncycle이 D / slah007이 I를 짜서 맞았다. 나도 G가 풀렸길래 읽어보았는데 별로 어렵지 않아서 빠르게 AC를 받았다. 쉬운 문제들을 페널티 없이 아주 빠르게 밀었고, 아마 이때 스코어보드에서 1등이었던 것으로 기억한다.

 

~1:56 (6솔브)

남은 문제들은 쉽지 않았다. 나는 E를 계속 보았는데 관찰을 여럿 했는데도 진전이 되지 않아 답이 없이 어려운 문제로 결론내렸다. 그 사이 kwoncycle은 A와 H를 읽었다. A가 수학이라길래 A 보라고 했는데 H가 더 재미있다고 하길래 그냥 놔뒀다. 가장 가능성이 높은 것은 slah007의 L이었는데, 컴퓨터가 빈 사이 코드는 완성했으나 시간 복잡도를 확신하지 못하는 상황이었다. 내가 페널티도 좋으니 그냥 솔브수를 믿자는 주장으로 제출 버튼을 반강제로 눌렀다. 오래 돌더니 다행히 AC를 받을 수 있었다. 이후 slah007은 K, M을 읽으러 떠났다.

 

~2:56 (7솔브)

각자 읽던 문제에서 별 진전이 없어 문제를 공유하기로 했다. 우선 내가 기하 문제인 J를 해석해 주었는데, 뭔가 팀원들과 얘기하다 보니 풀이가 술술 나와 거의 완성되었다. 마무리 부분이나 케이스워크는 kwoncycle이 잘하는 부분이라 넘기고 나는 slah007에게 M을 들었다. 풀어본 문제와 유사한 형태라 듣자마자 풀이가 나왔고, J 코딩이 끝나면 들어가기로 했다. 다행히도 kwoncycle이 J를 1번에 맞아왔다. (이때의 업적은 이후 2주간 귀에 얹히도록 듣게 된다)

 

~5:00 (8솔브)

M을 빠르게 짰지만 WA를 받았다. 오타를 몇 번 고치고도 같은 결과라서 우선 프린트하고, slah007의 사풀에 컴퓨터를 양보했다. 남은 시간 동안은 M을 좀 생각하다가 관찰이 틀렸나 싶어서 E도 보고 kwoncycle의 H도 조금 도왔지만 너무 어려운 것 같았고, 어떻게든 M을 마무리하기로 했다. 다행히도 종이를 열심히 쳐다보다 그냥 DP식이 틀렸다는 결론을 얻었고, 고쳐서 맞을 수 있었다. 남은 시간 동안은 slah007이 K를 최대한 짰으나 안타깝게도 WA와 TLE를 계속 받으며 끝났다. 

 

 

 

 

카이는 항상 강한 팀들이 많고 심지어 외부 팀도 있어서 상을 기대하고 가지는 않았는데, 셋이 유리했던 덕에 외부 팀 1등으로 특별상을 받을 수 있었다. 상품으로는 귀여운 넙죽이 수건을 받았다. 뭔가 쓰기 미안해서 기숙사에 잘 모셔두고 있다.

 

문제별 요약

문제	풀이	코딩	비고
A (D3, - )			어려운 수학 문제라고 한다.
B (G2, 0:24, +)	kwoncycle	kwoncycle	재미있는 constructive 문제이다. kwoncycle이 잘 풀어주었다.
C (D2, - )			대회 중에 잠깐 보았는데 문제의 철학을 이해하지 못했다.
D (P5, 0:48, +)	kwoncycle	kwoncycle	재미있는 constructive 문제이다2. kwoncycle이 잘 풀어주었다.
E (D1, - )			갓문제이다. 세팅이 재미있어서 오래 보았는데, 풀이의 핵심에 다가가려면 여러 역경과 고난을 거쳐야 한다. 업솔빙 예정
F (G4, 0:22, +)	slah007	slah007	간단한 게임 문제이다.
G (G3, 0:54, +)	leo020630	leo020630	교육적인 이분 탐색 문제이다.
H (D3, - )			지옥의 케이스 워크 문제라고 한다. kwoncycle이 대회 중에 꽤 많은 시간을 투자했으나 풀지 못했다.
I (G1, 0:48, +)	slah007, kwoncycle	slah007	까다로워 보이는 확률 계산 문제이다.
J (P1, 2:56, +)	kwoncycle, leo020630	kwoncycle	애드혹한 기하 문제이다. 관찰과 케이스워크를 여럿 한 후 정수론을 이용해 답을 구성하면 된다.
K (D5, - )			대회 중에는 풀지 못했고, slah007이 조금 고쳐 업솔빙했다.
L (D5, 1:56, +)	slah007, leo020630	slah007	교육적인 트리 DP 문제이다. 점화식은 굉장히 trivial하지만 시간 복잡도는 그렇지 않다.
M (P1, 4:35, +4)	leo020630	leo020630	관찰을 하나 하면 이 문제와 완벽하게 같은 꼴로 바뀐다.

 

thanks to) H를 제외한 문제들의 풀이가 https://azber.tistory.com/37 에 상세히 정리되어 있다.

 

느낀 점

 

M을 한 번에 맞고 K를 풀었다면 우승도 가능했기 때문에 조금은 아쉽지만, 첫 술에 배부를 수도 없고 1,2등 팀이 워낙 쎄서 결과 자체는 매우 만족스럽다. 외부 팀이 참여할 수 있는 대학 대회가 얼마 없는데, 좋은 경험 할 수 있도록 만들어주신 RUN 운영진들과 좋은 문제 만들어주신 출제진들께 감사드린다. 포스텍도 이렇게 진행해보고 싶다는 생각은 있지만 지리적 이슈로 힘들 것 같아 아쉽다.

 

모두 수고하셨습니다~