ACM-ICPC 2021 인터넷 예선 후기
28 Oct 2021Internet Preliminary Contest / ACM-ICPC 2021
10월 9일 ACM-ICPC 2021 인터넷예선에 참가했다. 나(eff3ct)랑 동기님들 두분(onkkno, witoru79)님이서, 경험이나 쌓아보자라는 생각으로 새내기팀을 꾸려서 참가했다. 여튼.. UCPC에 참가할때 썼던 팀이름 그대로 Mu_Ji_Sung_-_-_-으로 참가했는데, 나중에 보니까 이름 겹치는 팀이 꽤 됐다. 아무래도 우리처럼 이름짓기가 귀찮았던게 아닐까
결론부터 말하자면 아쉽지만 본선엔 진출하지 못했다. 우리 팀은 학교 6등 전체 76등을 했당. 뭐 새내기 치곤 3솔해서 괜찮은거 아닌가 싶다는 생각이긴 하다.
사실 나는 4솔을 목표로 하고 나온거긴 한데, CP 경험이 많이 없어서인지 그건 역부족이었다. 우리 팀이 풀어낸 문제는 I, J, K이다.
I : Sport Climbing Combined (Silver 5)
스포츠 클라이밍 콤바인드 무슨 어쩌고 저쩌고 .. 사실 딱 시작하자마자 이 문제먼저 펼쳐봤다. 한분은 인쇄를 하러 나가셨구 나머지 남은 분이랑 함께 문제를 봤는데, 영어로 써져있으니 어질어질해서 무슨소리인지 도대체 잘 안들어오길래 그냥 인쇄물을 기다리고 있었다. 그래서 인쇄물이 왔을때 딱 보니, 의외로 한국어 번역페이지가 있어서 그걸 읽고 바루 std::tuple로다가 그냥 sort하고 답 찾아내고 제출했다. (12 min) 좀 늦었긴 했는데 여튼 한문제 풀고 신났었다.
J : Ten (Silver 1)
나는 다른 문제를 읽고 있었는데, onkkno님이 이거 쉬워보인다구 하시면서 문제를 푸셨다. 대충 행으로 prefix sum 찾아서 10이 되는지 찾는 방법이었던거 같은데 시간초과였나 그냥 WA였나 여튼 그게 떠서 내가 다시 문제를 보고 조금 생각을 했다. 잘 보니까 제약이 작게 걸려있어서 대충 \(\scriptsize O(n^{3})\)정도에 문제를 풀 수 있을것 같아서 그렇게 고쳐서 제출했더니 AC를 받았다. (79 min) p_ij값이 1~10만 가능하다는 점이 복잡도를 낮출 수 있다는걸 늦게 알아서 여튼 조금 늦긴 했다. 그냥 2차원 상에서 prefix sum을 sum(i, j) = 1행 1열부터 i행 j열까지 합으로 하면 \(\scriptsize O(n^{2})\) 으로 해당 테이블을 채울 수 있구. 포함배제의 원리를 활용해 각각 세그먼트들에서 합을 구한 다음 10이랑 비교하는식으로 적당히 짜주면 쉽게 풀 수 있는 문제였다. 여튼 여기까지 풀고 나니 음.. 뭔가 이제 풀 수 있는 문제가 없어보였다.
K : Treasure Hunter (Platinum 4)
보물 헌터 <- 이 문제를 푼건 조금 의외였다. 왜냐면 난 그리디 개념이 들어가는 문제들 잘 못풀어서.. ㅋㅋㅋ 머리가 셋이나 있으니 운이 좋게도 풀어진 것 같다. witoru79님이 먼저 접근법을 말해주셨는데, \(\scriptsize O(n^2)\)짜리라 TLE확정인 방법이었다. 그래서 조금 고민하다가 1시간이 슥 지나가고, 왠지 보니까 이거 보물 좌표만 보면 될 것 같네 라는 식으로 접근을해서 \(\scriptsize O(n)\)정도로 복잡도를 낮출 수 있었다. 이 때가 30분인가 40분 남겨둔 시점이었는데, 이걸 구현해보겠다구 노트북 잡고 대충 슥슥 구현해보는데, 잘 안되서 코드짜는걸 onkkno님께 넘겼다. 뇌절을 계속 하던 내 코드를 샥샥 고치시더니 야무지게 예제가 다 잘 나오는것을 확인하고 제출했다. 그리구 AC (160 min). 사실 20분 남긴 시점에서 이제 풀 수 있는 문제가 없음을 직감하고, 스코어보드 구경하다가 예선이 끝이 났다.
사실 B, E, H번도 해보려고 시도는 했었다. 특히 B번, 약간 교과서에 나올법한 문제여서 예전에 수능 수학 30번문제들에 이렇게 개수 세는 문제들이 있었다. 그래서 그 문제들 접근이 대충 경계선 좌표들만 알아내서 포함배제 비슷하게 풀어내는거라, 걍 그것처럼 풀면 되지 않을까 싶었다. 케이스가 조금 많기도 했고, 또한 구현을 하려니 극좌표계로 써야하나 뭔지 잘 모르겠어서 구현을 미루다가 결국엔 못풀었다. ㅜㅜ 푼 사람들 얘기하는거 보니 풀이가 그게 맞다고.. 여튼 젤 아쉬운 문제 ㅋㅋ 4솔했으면 본선 진출해볼수도 있었는데 까비 아깝소..
E번은 읽으면서 흠 왠지 구간으로 DP 테이블을 채우면 풀 수 있을거라 생각하긴 했는데, 딱 DP테이블 정의를 어떻게 해야할지 모르겠어서 그대로 넘겼다. ㅋㅋ solved.ac 티어는 플래티넘 3인데 dp문제는 골드5만 되어도 버거운 사람이 어캐 이걸 대회시간에 풀겠는가. 쪼금 아쉽긴 했다. 사실 DP좀 연습해보겠다고 tag:dp 해놓구 쉬운것부터 차근차근 대회전에 조금 풀었었는데, 크게 의미있진 않았다. 하루만에 DP 고수가 될 수는 당연히 없으니까 ㅎ;;ㅋ
H번두 뭔가 읽다보니 세그먼트 트리를 써서 풀면 되지 않을까 싶었는데, 이게 순서쌍이 3개짜리를 찾아야해서 그렇게 쉽진 않았다. ㅋㅋ 세그트리 좀 열심히 파둘걸 그랬나 하는 생각이 맴돈다.. 여튼 이 3문제가 대충 접근방향은 맞았는데 AC까지는 못했던 문제들이라 아쉽긴했다.
우리학교는 올해는 4솔까지 본선에 진출하게 되었다. 그래도 머 새내기팀 치고 3솔이면 잘한거아님? ㄹㅇㅋㅋ 다음해 예선엔 꼭 본선 진출할 수 있길 기원해본당. 본선 진출한 한양대팀들 파이팅~~~