[대회] 2022 ICPC Seoul Regional 예선 후기
후기를 쓰려고 했는데, 벌써 예선이 끝난지 일주일이 되었다...
교내 대회 준비와 과제에 치여 후기글을 쓸 겨를이 없었다.
정수론 과제를 하다가 하기가 싫어진 김에 간단하게 글을 써본다.
먼저, 이번 예선은 부득이하게 2인 팀으로 참가하게 되었다.
우리 팀은 매주 목요일 팀연습을 했었다.
대회 이틀 전 목요일에도 팀연습을 하기로 했었는데, 갑자기 Picasso 선배가 코로나에 걸렸다고 하셨다.
그래서 팀연습 못하겠네...라는 생각을 했는데 생각해보니까 대회도 못나갈 상황이었다.
바로 대회 본부에 문의 넣어서 2인팀으로 참가가능하냐고 물어봤더니, 가능하다하셔서 semteo04선배와 나 둘이서 참가하게 되었다....ㅋㅋ
본선에 못갈까봐 많이 무서웠는데 다행히 좋은 결과를 받았다.
운이 좋게도 전체 18위, 학교 1등으로 본선에 가게될 것 같다 ㅎㅎ;
이번 셋이 좀 특이한 난이도 분포를 가져서 운이 좋게 높은 등수를 얻게 된 것 같다.
물론 semteo 선배가 잘한 것도 있다.
2인팀이 되면서 전략을 좀 수정했다.
어려운 문제가 나오기 전까지는 그냥 semteo 선배가 계속 구현을 하는 식으로 전략을 짰다.
어차피 문제읽는 건 실력 차이가 크게 나지 않는데, 푸는 건 실력차이가 나기 때문에 주로 내가 문제를 읽는 방식으로 진행하기로 했다.
그리고 이번 셋에서 이 전략은 대성공이었던 것 같다.
초반 문제들이 크게 어렵지도 않아서 내가 읽으면서 풀이가 나온 문제들이 많고, semteo 선배가 워낙 잘 해주시니까... 빠르게(81분) 6솔을 했던 것 같다. 잘 기억이 나진 않지만 6솔 직후에 15위? 근처였던 것 같다. (패널티가 구려서 이후에 쭉 내려오긴 했다...ㅎ)
제출 기록과 코드를 볼 수 없고, 벌써 1주나 지나서 잘 기억이 나지 않는다...
A. Balance Scale [0:15] AC
C. Container Rearrangement [0:19] +2, AC
두 문제가 한글문제여서 먼저 보았다.
C가 좀 끌려서 먼저 보았다. boj.kr/24249와 굉장히 비슷하게 생겼어서 끌렸던 것 같다. 근데 막상 읽어보니 다르긴 했다 ㅋㅋ
1. 서로 1칸씩 차이나야 한다.
2. 바로 옆칸으로 옮기는 게 아니라 아무 곳으로 옮길 수 있다.
를 강조해서 전해드렸고, semteo 선배가 바로 짜서 내셨는데 2번인가? 틀리셨다.
나는 와중에 A가 풀린 걸 보고 읽었다. 읽어보니 엄청 쉬웠다.
옆을 보니 semteo선배는 C를 틀려서 멘탈이 나가있어 보였다.
C 한 번 더 본다고 하셨던 거 같은데 내가 그냥 A번 짜라고 꽤 강하게 얘기했다... ㅎㅎ;
1. 가벼운 쪽에만 올릴 수 있다.
를 강조했던 기억이 있다.
암튼 바로 A를 짜셔서 한 번에 AC 받았다.
나는 E랑 K를 읽으러 갔고, 선배는 다시 C보시더니 자책하면서 AC를 받아오셨다. 잘은 모르고 뭐 간단한 실수였던 것 같다.
E. Gift Discount [0:26] +2, AC
C번 맞으시자 마자 해석해 드렸다.
바로 짜러 가셨고, 2번 틀리시고 AC 받아오셨다.
굉장히 사소한 실수때문에 틀려서 멘탈이 굉장히 나가 있으신 것 같았다...
여담으로, C를 맞고 나서 E를 맞기까지 한 20분은 썼던 것 같은데, 지금 보니 7분밖에 안 썼다는 게 믿기지 않는다 ㅋㅋㅋㅋ;;;
둘 다 굉장히 급했던 것 같다....
K. Temporal Graph [0:55] +3, AC
G. Jar Game [1:03] +1, AC
E를 풀고 한 15분? 정도 둘 다 문제를 읽었던 것 같다.
나는 K를 먼저 보았는데 해석하는 게 쉽지 않았다.
아마 K가 조금 풀려서 둘이 풀이에 대해서 얘기를 했던 것 같다.
처음에 해석을 잘 못해서 T마다 한 번 이상 이동할 수 있는 줄 알았다.
그래서 일단은 어려운 것 같아서 다른 걸 먼저 보자고 했다.
스코어보드를 보니 어려운 것 치곤 너무 많이 풀렸던 것 같아서 다시 꼼꼼히 읽어 봤는데, 시간 별로 한 번만 이동할 수 있는 걸 발견했고, 그냥 dp?느낌으로 한 번씩 하면 될 것 같다고 얘기가 나와서 선배는 바로 풀이를 짜러 갔다.
나는 G를 읽었고, 너무 게임 dp 같았다.
읽으면서 정리하다보니까 dp[100][100][100]으로 짜면 될 것 같았다.
선배가 K 다 짜면 알려줄 생각으로 손으로 간단하게 수도코드를 짰다.
와중에 선배가 K번을 여러번 틀리셔서 같이 보게 되었다. 풀이는 확실히 맞는 것 같았는데, 계속 틀렸다.
잘 기억 안나는데 배열 사이즈에서 틀렸었던 것 같다. 선배는 그걸 고치고 있었다.
나는 K번 여러번 틀려서 내가 G번 풀이 나왔으니까 G번 보자고 했다.
그래서 바로 G번 풀이 알려드리면서 선배가 옆에서 짰다.
예제가 잘 나와서 바로 냈는데, 틀렸다.
내가 재귀함수 돌면서 턴을 변수로 넣고, dp는 100*100*100으로 알려드렸는데, 생각해보니까 서로 다른 값을 가질 수 있더라.
근데 대충 생각해보니까 턴이 50도 안되는 것 같아서 그거 dp에 넣어서 짜야한다고 했다. 바로 맞았다.
내 멍청함 이슈로 패널티 하나 쌓았다 ㅎ;
암튼 G번을 맞추고 다시 K번 보았다.
코드 보니까 아까 고친 코드 내면 맞을 것 같아서 제출했다.
근데 이미 K번을 맞은 상태였다(?)
아까 G번 보기 직전에 다시 내셨었고, 그게 AC였던 건데, 정신이 없으셔서 못 푼 걸로 까먹으셨던 것 같다...ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
F. Islands Tour [1:21] +1
내가 해석했는데 읽으면서 어느정도 풀이가 나와서 바로 알려드렸다.
1. 가장 긴 경로 찾으면 된다.
2. Outdegree는 무조건 1 or 0이다.
3. 한 번 갔던 곳은 또 못 간다. 싸이클 만나면 그 싸이클 돌고 끝날 수밖에 없다.
정도를 알려드렸다.
선배가 듣자마자 dfs+dp 풀이를 알려주셨고, 무조건 맞는 것 같아서 제출했다.
근데 틀려서 어디서 틀렸는지 좀 봤는데, 0 base로 주어지는데 그 부분 처리가 잘 안되었더라.
고쳤더니 맞았다.
이거 맞췄을 당시에 20위 안쪽이었던 것 같은데, 패널티가 너무 구려서 무조건 역전당할 거라 생각했다.
작년 기준으로 서강대에서 본선에 가려면 학교 2등에 들어야 하는데, 바로 아래 두 팀이 5솔이라 역전당할까봐 무서웠다.
J. Rectangles [2:55] +2
F를 풀고 나서 우리는 이 문제에 올인했다.
1시간이 넘는 시간동안 3개 정도의 N^2 풀이가 나왔다 ㅋㅋ
근데 진짜 답이 안나오더라.... 대회 종료 20분 정도 남기고 어차피 새 풀이 나와도 시간 부족할 것 같으니 뚫릴만한 N^2짜보자고 했다.
풀이는 대충 뭐냐면 한 점을 잡고 그 점의 오른쪽 윗 쪽에 있는 점들을 그래프 탐색 느낌으로 탐색하면서 만족하는 개수를 누적해서 세는 방식이었다. 말로 하니까 어려운데, 걍 대충 잘 탐색하는 풀이었다.
이 풀이 자체가 탐색하는 경우가 생각보다 많지 않을 것 같아서 이걸 짜기로 했다.
냈는데 어림도 없이 TLE 받았다. (1번 제출)
선배는 컴으로, 나는 인쇄해서 코드에 시간 줄일만한 거 있는지 확인했다.
이때부터는 시간이 10분도 안남아서 무지성으로 제출하고 확인도 안했다. 채점이 꽤 길어서...
선배가 불필요한 연산 몇 개를 삭제하시고 제출하셨다. (2번 제출)
그 코드를 제출하고 나서 내가 continue를 사용하던 부분을 정렬+break로 바꿀 수 있다고 했고, 그걸 고쳐서 냈다. (3번 제출)
3번 제출 할 때, 2번 제출이 TLE인 것을 확인했다... 절망적이었다.
한 5분 남았었고, 선배는 map을 안 쓰고 1차원 배열 큰 걸 이용할 수 있다고 하셨고 그걸 고쳐서 내려고 ALT+TAB을 하셨는데, 3번 제출이 AC 받아 있더라......
진짜 짜릿했다... 둘이 막 좋아서 하이파이브 했던 기억이 난다..
J번을 N^2 커팅으로 뚫어서 운 좋게 좋은 성적을 얻을 수 있었다고 생각한다.
또, 앞 6문제가 다 브실골이고 그 다음이 갑자기 엄청 어려워지는 문제 셋이었는데, 이게 2인팀인 우리한테 좋게 작용했던 것 같다.
3인 1컴에 문제 셋이 저러니까 2명이어도 딱히 불리한 점이 없었던 것 같다.....
어찌되었든 좋은 성적을 받아서 기분이 좋다...
semteo 선배 정말 잘 푸시더라. 굳...
끝나고 학회원들이랑 통큰갈비 회식을 했다. tksvlf123 선배가 열심히 고기를 구워주셨던 게 기억에 남는다...ㅋㅋ
밤에는 djs100201, raararaara선배랑 치맥을 하며 이런저런 얘기를 많이 했다.
행복한 하루였다...
https://dong-gas.tistory.com/33?category=979610 작년 ICPC 예선 후기글인데, 많은 생각이 든다. 1년 사이에 많은 일이 있었다... ㅎㅎ;
본선에서도 좋은 결과가 있으면 좋겠다!
열심히 해보자.