[대회] 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년 사이에 많은 일이 있었다... ㅎㅎ;

 

본선에서도 좋은 결과가 있으면 좋겠다!

열심히 해보자.