2025 ICPC 예선 후기

우연히 친구의 소개에 도움받아 PS를 제대로 한지 3달이 지났네요...

지금이라도 블로그 하나 만들어서 성장과정이나 그냥 하고 싶은 얘기 일지처럼 정리하라고 만들었습니다 하핫

 

동아리에도 가입하면서 몰랐던 컴공 친구들과도 알게 되면서 ICPC 참가를 하게 되었습니다...

 

대충 팀 소개를 하자면

 

jkrt2 (BOJ trashmouse0524) - 접니다. 타자는 빨라서 스피드에 자신은 있는데 구현 실수나 기복이 심함

a_cedia (BOJ tjrn3712) - 애드혹 문제 고수, 팀연습 두 번에서 둘 다 유일하게 플레 솔브를 했어요

additionalpass05  - 올라운더, 비교적 어려운 문제 발상을 잘 잡아요 (SUAPC 때 같은 팀이였는데 플레 퍼솔 전적 있음)

 

닉 색을 보면 알겠지만 현재 셋의 코포티어가 모두 블루여서 팀명을 3Blue1Nutella로 짓게 되었습니다.처음으로 팀연습까지 하고 온 대회고 (처음 참여한 SUAPC는 디코방에서 팀원 구하던 분들과 같이 하느라 대회 전에는 대면으로 만난적도 없음), SUAPC 경험이 은근 성공적이였기에 (어쩌다 팀이서 같이 Diamond 5  문제를 풀었습니다. 어케 함?) 내심 기대를 하고 있었어요.

 

팀노트도 처음으로 만들어봤는데 저는 알고리즘을 배우면서 정작 템플릿을 만든 적이 별로 없습니다.그래서 대충 백준 문제 솔루션 복붙해서 팀원한테 넘겨줬어요. 지금부터라도 약간 정리를 제대로 해야 할 듯...

 

예비소집 (Oct. 10)

예비소집에서 특별히 크게 한 건 없고 시험 환경이나 테스트했습니다.

느낀 점

1) Python은 쓰지 말자. 특히나 여기서는.  (아니 1초 안에 array 탐색 + 뺄셈 3000만번을 못 하는 건 너무한 거 아니나요)

(사실 이건 저는 C++ 중심으로 해서 알빠노이긴 한데 다른 분들이 Python도 같이 써요)

2) 마우스가 어딘가 이상했다. (Ctrl + C 3번 해서 3번 다 마우스가 자동으로 선택해제해서 실패함)

뭐 당일 날에 익숙해져야지 하는 마인드로 했습니다.

 

예비소집 이후 코포를 쳤는데 대략 2000짜리 퍼포를 찍었습니다. D 풀었으면 2200 정도도 가능했을 거 같은데 DP 초기조건을 INF가 아니라 0으로 해서 틀렸어요. 아쉬운 거죠

그런 멍청한 실수는 팀원이 잘 해결해주겠지라 믿고 잤습니다.

 

본대회 (Oct. 11)

 

팀원분들이 커피를 사오셔서 저의 수면부족을 해결해주셨어요 야호 (진행자 분들이 준비해주신 복숭아 주스도 맛나게 마셨습니다 😉)

VSCode로 문제파일 만들어가면서 준비하고 대회가 시작했습니다. 사실 이미 본지 하루가 지나서 정확한 서순은 기억이 잘은 안 나나 최대한 기억나는 대로 적었어요

 

0 / 180 (0 AC 0 WA)

문제를 A - D는 pass님이, E - G는 제가, H - J는 acedia님이 분할해가면서 시작했어요. 운 좋게도 가장 쉬운 F가 제 손에 들어와서 바로 코딩을 시작했습니다.

근데 1번 WA가 떴어요. 알고 보니 처음 시작하는 자연수에 아예 0이 없다는 가정으로 시작해서 틀렸습니다. 그래서 leading 0까지 잘 고려해서 푸니까 맞았어요. 예제에 0이 안 들어간 게 좀 컸던 거 같네요. 제가 바보여서 틀렸습니다라 하려고 했더니 제가 적게 틀린 거였습니다 어라? (아래 사진은 우리 주변 순위 F 성적표에요. 1트가 하나도 없습니다)

 

9 / 180 (1 AC 1 WA)

F를 푸는 동안 나머지 팀원이 A를 풀다가 O(N^2)이 가능하다는 점을 알게 됐습니다. 대충 그리디라는데 그냥 팀원 분들 말 듣고 따라하기만 했어요. 이게 왜 정답인지는 전 잘 모르겠음 하핳 (그리디 너무 어려움...)

이걸 풀고 나서 전체 순위가 8위였나 그랬는데 아무래도 F 때문인 거 같습니다. 

 

16 / 180 (2 AC 1 WA)

그 후 고전을 약간 했습니다. I가 남은 마지막 한국어 문제라 풀려고 했는데 아무리 생각해봐도 뚜렷한 패턴이 나오지 않는 것입니다. 대충 k의 약수 수 곱하기 2 아니냐라 주장해서 작은 수로 해본 다음에 PBA로 쌀먹해보려 했으나, 처음에는 약수 개수를 잘못 구현하고 (for문 매개변수를 잘못 잡았어요), 다음에는 그냥 답이 틀려서 WA 2스택이 쌓였습니다. 그걸 보고 그냥 다른 문제부터 보고 a_cedia님이 I에 집중하는 걸로 했습니다.

 

50? / 180 (2 AC 3 WA)

나머지 문제를 보다가 슼보에 H를 푼 분들이 많아서 가봤는데 아무래도 기하인 거 같아서 건너뛰고 그냥 문제를 돌아보다가 additionalpass님의 J 솔루션이 나왔습니다. 4-cycle이 2-edges path 2개의 합임을 이용해서 탐색을 하면 된다고 하더라요. 솔직히 TLE 걱정하면서 코드를 짰는데 운좋게도 1트 안에 맞았습니다. 대회 끝까지 시복이 얼마인지도 모른채로 있었지만 나중에 찾아보니 O(n^3)이였다고 생각한게 알고 보니 O(nm) 안에 가능하다고 하더라요. m 제한이 25000였던 이유가 그거였던 것...

 

72 / 180 (3 AC 3 WA)

이 상태에서 뚜렷한 풀이가 잠시 안 나오다가 갑자기 H 그림을 보면서 '아 이거 LIS'구나 라는 생각이 바로 들었습니다. 풀이는 알겠으나 이제 문제가 NlogN LIS 풀이가 생각이 안 났습니다. 어쩌다 제가 팀노트에 넣지도 않았더라고요. 근데 다행히도 additionalpass님이 기억을 하고 계셔서 그 전 파트는 제가 구현하고 그 분에게 컴을 넘기...려 했더니 I에도 마침내 풀이가 나왔습니다! 대충 식 가지고 장난치면 된다 해서 구현을 a_cedia님에게 맡겼는데 어디 구현 방법이 잘못됐는지 예제 답이 제대로 안 나왔습니다.

 

그래서 다시 H로 돌아가니 팀원분이 LIS를 잘 구현하고 있었는데 upper, lower_bound 함수의 존재를 모르고 있어서 직접 이탐 중이였더라고요... 마치 소트 함수 직접 구현하던 제가 생각나네요 흑흑

그래서 그 분한테 NlogN LIS 풀이를 배우고 직접 구현을 하여 H를 맞췄습니다. 이 과정에서 제가 H 풀이를 생각할 때 잘못된 점을 찾아서 중간에 WA가 안 뜬 게 다행이네요

 

103 / 180 (4 AC 3 WA)

그 직후 a_cedia님의 I 풀이를 살짝 다듬어서 제가 간단하게 구현할 수 있는 형식으로 만들어서 고쳤더니 맞췄습니다. 그렇게 5솔에도 성공 (솔직히 I가 한국어 번역이 주어질만큼 쉬운 문제는 아니라 생각해요, 그거 때문에 시간 날린 팀들이 꽤 될 거 같네요)

 

113 / 180 (5 AC 3 WA)

그 이후로 두 팀 이상 푼 문제가 C밖에 없어서 C를 보기로 했으나 아무리 봐도 많조분인 거 같아서 많조분이 하도 싫었던 저는 혹시 좌표압축으로 가능할까라고 제안하니 a_cedia님이 특정 move 수 안에 항상 해결됨을 제안하여 이에 브루트포스 방식을 추가하고, additionalpass님이 그 문제를 BFS 문제로 바꾸면서 TLE가 안 날 수 있다고 못을 박아버렸습니다.

그 정보를 이용하여 구현을 시작했는데, 이 BFS 관점으로 바라봐도 구현 과정이 '많조분'성이 있었습니다.

이 과정에서 제 PS/CP 인생 처음으로 일반 변수에 대한 포인터를 제대로 활용해봤습니다. 최소, 최대인 변수 (R, G, B)의 주소를 저장하니 구현 실수를 할 수 있는 일이 더욱 줄었습니다.

 

그런데도 런타임 에러가 떴습니다. 왜인지 헤메다가 a_cedia님의 디버깅 덕분에 이번에도 for문 매개변수 때문에 틀렸음을 알게 됐습니다...

for(i = ...)

   for(i = ...)

이렇게 적어놓았어요.

 

160? / 180 (6 AC 3 WA)

다행히 그걸 고치고 나니 한 번 안에 AC가 160분경에 뜨며, 풀 수 있는 문제는 다 풀었다 판단해서 나머지 문제는 감상 정도만 하다가 끝났어요

 

Final 

- Freeze 전 36위 (Freeze 이후 1 AC), 연세대학교 中 4위 (Freeze 이전엔 3위이나 Severance 팀이 7솔을 하면서 밀렸습니다 ㄷㄷ...). 뭔가 큰 일이 없다면 본선에 진출하기에 충...분하겠죠?

Edit (Oct 14) - 프리즈가 풀린 이후 28위로 올라갔습니다. C WA 없이 잘 해치워서인지 생각보다 많이 올라갔네요 

 

소감

팀 대회를 한 게 지금이 두 번째여도 은근 초심자의 행운이 따라주어서인지 팀원 분들도 잘 따라주고 답도 이해하기 쉽게 알려주면서 6솔에 성공하게 됐습니다.

개인적으로도 문제 구현 6개를 모두 맡으면서 1인분은 했다고 자부할 수 있는 점이 좋았습니다. 다만 본선에서 for문 매개변수 잡아서 틀리는 멍청한 실수는 줄여야 될 거 같아요.

 

여담으로 이 날 인쇄된 상태의 팀노트를 처음으로 봤어요. 마침 페이지 수가 남아서 a_cedia님이 채워주신 마지막 페이지의 사진으로 이 포스트를 마칩니다.

갓이에요!