Camp Contest 2021 Summer 후기
Camp Contest
7, 8월 ICPC Sinchon 여름 캠프의 마무리이자 SUAPC의 모의고사 격인 Camp Contest가 3시간에 걸쳐 치러졌다.
최종 등수는 2등으로, 아주 만족스러운 결과였다.
1등이 4솔, 2등부터 5등까지 3솔로 엄청나게 치열했다.
시험 도중에 문제들이 너무 어렵다고 생각했는데, solved.ac 기준 플레티넘 5문제, 골드 1문제, 실버 1문제로 객관적으로도 어려웠던 시험이었다.
타임라인
00:09 A (permutation making) : AC
조금 생각해 보니, 합해서 n이 되는 쌍들을 인접하게 구성하면 됨을 알 수 있었다.
이후 B (짝수싫어수)를 봤는데, k번째 수 (DP)라서 바로 넘어갔다.
그리고 C (안산 탐지기)가 인터렉티브였는데, 한 번도 인터렉티브 문제를 풀어본 적이 없어서 또 넘겼다.
00:50 D (신촌 수열과 쿼리) : 1TLE
2번 쿼리가 꽤나 참신한 세그트리 문제였다.
우선 (minimum value, total sum)을 노드로 갖는 세그트리를 만들어줬다.
처음엔 별생각 없이, minimum value가 j 이상인 구간들을 모두 구하고, 이를 이어붙여 i가 포함되는 구간의 총합을 구했다.
당연히 TLE가 떴다.
00:59 D (신촌 수열과 쿼리) : AC
i를 기준으로 왼쪽, 오른쪽에서 이분 탐색을 통해 최솟값이 j 이상인 구간을 최대로 구해주면 될 것 같았다.
항상 이분 탐색을 구현할 때 불안불안했는데, 다행히도 한 번에 AC를 받았다.
D를 푼 직후 스코어보드를 봤는데 A, B, D만 풀려있었다.
아마 이때 1등이 youx님, 2등이 surface_03님, 3등이 나, 4등이 portal3046님이었을 것이다.
상위권이 모두 연세대였고, 2등 4등이 SUAPC 같은 팀이었기 때문에 엄청나게 자랑스러웠다.
이에 힘을 얻고 E를 풀기 시작했다.
01:27 E (미팅) : 1TLE
문제에 국렬님이 나오는 것으로 보아 분명 플로우 문제였다.
강의 마지막 주 주제가 플로우라, 최근에 플로우 문제만 왕창 풀어서 자신만만했다.
사실 저 당시 Flow 1만 복습했고, Flow 2를 복습하지 못한 터라 홀의 결혼 정리를 떠올리지 못했다.
그래도 flow network를 구성해 준 뒤, 최대 유량을 흘려준 후 매칭이 되지 않은 남성들과 그들로부터 alternating path를 통해 도달할 수 있는 남성들을 선정하면 된다고 생각했다.
그러나 TLE가 떴다.
01:45 E (미팅) : AC
이건 파이썬이 파이썬 한 것이라고 되뇌며 C++로 코드를 그대로 짰다.
로직엔 문제가 없다고 생각했고, 이보다 더 빠르게 할 방법도 생각나지 않았기 때문이다.
“채점 중”을 보며, 정말 맞았으면 좋겠다고 수십 번 생각했다.
얼마 후, “정답입니다”가 떴고, 퍼솔이었다.
첫 3솔이었고, 1등에 안착했다.
이후 F (여행사 운영하기)를 봤는데, 트리 DP인가 싶었는데 해설을 듣고 나니 SCC로 묶은 후 DAG에서의 DP였다.
정말 일말의 아쉬움도 남지 않는 문제였다.
그리고 마지막 문제인 G (신촌방위본부)를 봤다.
미사일들이 떨어진 좌표로 볼록 껍질을 만든 후 볼록 껍질 내부에 있는 나무의 수 - 볼록 껍질 내부에 있는 보호막 수를 구하면 되는 문제였다.
보호막이 없더라도 어렵지만 어떻게 풀어볼 생각은 했을 것 같은데, 보호막까지 카운트하려니까 머리가 새하얘졌다.
사실 구글링을 통해 픽의 정리까지도 알게 되었고, 볼록 껍질의 각 변 위 격자점 수들도 gcd를 활용해 세면 되겠다 싶었는데, 500,000이라는 거대한 수 앞에서 파이썬이 제 기능을 해줄 수 있을까 의문이었다.
또한 C++로는 볼록 껍질을 짜본 적이 없어서 꽤나 시간이 많이 들 것 같았다.
그렇게 고민만 하다 보니 남은 1시간이 훌쩍 지나갔다.
프리즈 된 스코어보드 상에서는 1등이라 내심 우승도 기대했지만, 아쉽게도 wbcho0504님께서 4솔을 달성하시면서 2위로 밀려났다.
후기
7, 8월 정말 열심히 PS를 했다.
DP 2에서 1 문제, BCC에서 4 문제, Flow에서 3 문제를 제외하곤 모든 필수 문제와 연습 문제를 푼 것이 그 증거이다.
solved.ac 레이팅도 거진 500 정도 높였다.
돌이켜 보면 어떻게 두 달 동안 번아웃 없이 할 수 있었는지 의문이 들 정도이다.
이렇게 할 수 있었던 원동력을 꼽으라면, 첫째로 ‘재미’이다.
PS가 너무나도 재미있었다.
새로운 알고리즘을 알았을 때의 재미, 어려운 문제를 풀어냈을 때의 재미.
그래서 별 스트레스 받지 않고 즐기면서 할 수 있었다.
두 번째 원동력은 ‘성장’이었다.
solved.ac의 레이팅, 등수, 그룹 내 필수 문제와 연습 문제의 스코어보드, 그리고 마지막의 Camp Contest와 SUAPC까지.
스스로의 성장 정도를 지켜볼 수 있는 다양한 지표가 존재했고, 이는 곧 BOJ에 접속할 힘이 되었다.
물론 레이팅만을 위한 PS는 좋지 않지만, 연습 문제만 다 풀더라도 레이팅이 쑥쑥 올라 레이팅에 너무 목매지는 않았다.
돌이켜보면 2-sat이랑 flow가 제일 재밌었다.
2-sat은 문제들도 재밌었고, 문제의 진리집합을 Conjunctive Normal Form으로 만들어내는 과정이 그냥 set theory exercise를 푸는 느낌이었다.
그래서 티어 대비 체감 난이도가 낮아 더 좋아했던 것 같다.
flow도 2-sat과 비슷하게 느껴졌다.
둘 다 그래프를 어떻게 구상하는지가 문제의 핵심인데, 이 점이 잘 맞았나 보다.
반대로 DP와 bcc는 정말 고통이었다.
DP 1은 첫 주 차라 괜찮았는데 DP 2는 연습문제 풀다가 울 뻔했다.
사수아탕은 아직도 기억에 남는다.
DP가 문제 스타일이 정형화돼있지 않아서 더 어렵게 느껴진 듯하다.
bcc는 애초에 너무 어려운 개념이기도 하고, 파이썬으로는 도저히 못 해먹을 것 같다.
이때 C++로 갈아타야겠다는 생각이 정말 강하게 들었다.
개강을 한 터라, 종강 때까진 PS를 잠시 쉴 것 같다.
그리고 자료구조를 듣는 김에 java로도 PS를 해 볼 기회가 있을 것 같다.
겨울에 PS를 각 잡고 할 수 있을진 모르겠지만, 하게 된다면 C++로 완전히 갈아탄 후 아직 배우지 않은 알고리즘들을 더 섭렵해 볼 예정이다.
캠프 중급반을 수강할지는 모르겠지만, SUAPC는 아마 나갈 것 같다.
내 알고리즘 역사(?)에 큰 획을 그어주신 ICPC Sinchon 운영진분들께 매우 감사하다!
Leave a comment