2022 숭고한 연합 알고리즘 콘테스트 - Div 2 후기

스코어보드

 

2022 숭고한 연합 알고리즘 콘테스트에 Division 2로 참가해 2등을 수상했다. (빨갛게 빛나는 10틀) 아쉽긴 하지만, 대학 진학 후 첫 공식? 대회에 나름 좋은 성적을 거둬 기쁘기도 하다.

 

대회 전

Division 2의 참가조건은

 

• 숭실대 SCCC / 고려대 Alps / 고려대 Alkor / 한양대 Aloha 의 부원이면서
• ICPC, SCPC, UCPC, KOI 등 수상 X / solved.ac D3 미만 / Codeforces max rating 1900 미만

이며, 난 한양대 Aloha의 부원이고, 대회 수상이 없고, solved.ac P1, 코포 맥레가 1900이 조금 안돼서 Division 2에 참가했다.

 

대회 신청 후 공지를 읽어보는데 처음에는 zoom을 이용해 참가자 캠과 화면 녹화를 한다는 이야기가 있어서 좀 걱정했는데, 대회 전날 온 이메일에는 인터넷 검색을 허용하며 별도의 모니터링 없이 진행한다고 수정돼 있었다. 고등학교 2학년 초반 쯤 까지는 PS를 좀 열심히 하다 손 놓고 쉬엄쉬엄 한 지 거의 2년이 다 되어가서 연습을 좀 해야되나 걱정했지만, 인터넷 검색 허용이라길래 그냥 말았다.

 

온라인으로 치뤄지기 때문에 난 본가에서 참여했고, 4시간동안 진행될 대회에 대비에 대회 직전 니코틴 풀 충전 및 카페인 음료 한 캔 구매 후 책상 앞에 앉았다.

 

대회 중

문제는 A ~ H 총 8문제가 있었다. 난이도 순 일거라 믿고 A부터 열었다.

 

브론즈5가 하나 있었다. 예제도 안 돌려 보고 냈다. 퍼솔.

여담으로 나보다 늦게 제출한 코드가 먼저 채점이 돌아 스코어보드에 떴고, 퍼솔 놓친 줄 알았는데 나중에 보니 내가 퍼솔이더라.

A AC (0 : 00, First to solve)

 

B를 읽었다. 문제가 너무 길어 어지러웠다. 넘겼다.

 

C를 읽었다. 문제가 너무 길어 어지러웠다. 넘겼다.

 

D를 읽었다. 뭔가 적당한 그리디? constructive 문제같았다. 나중에 보기로 하고 넘겼다.

 

E를 읽었다. 처음에는 문제를 잘못 읽어 '연속으로 쉬는 날'의 최솟값의 최댓값를 구하라는 줄 알고 부분합 + 파라메트릭 풀이를 짰다. 예제가 안나오더라. 뭔가 잘못 짠게 있나 열심히 들여다 봤다. 맞는거 같았다. 한 30분쯤 씨름하다가 (예제를 손으로 풀어봤다면 잘못 읽었다는걸 일찍 알고 고쳤을텐데...) 말린 거 같아 나중에 보려고 넘겼다.

 

이때가 한 40분 시점. 시간을 한참 버려 걱정했는데, 스코어보드를 보니 1등이 ABC 3솔, 1솔인 나도 6위에 위치해 있었다. 패널티가 좀 걱정되긴 하지만, 극복 못할 차이는 전혀 아니며 문제 수로 벌리면 되겠다 생각했다.

 

F를 읽었다. 특정 정점들을 모두 지나는 최단경로...? 정점이 하나면 다익스트라 두번 돌리면 될텐데... 여러개면 어떻게 하지? 잠시만 이거 근데 TSP 아닌가? 순간 멘붕. 하지만 잠시 생각을 해 보니 어차피 무조건 그래프의 최단경로로 가야 의미가 있으니, '다익스트라를 돌리되 정점을 선택할 때 거리만 고려하는게 아니라 {거리, 지나온 특정 정점의 개수} pair로 비교'하면 되겠구나 하는 생각이 들었다. 열심히 짜고 1트에 맞았다. 퍼솔.

F AC (1 : 10, First to solve)

 

C로 돌아왔다. 열심히 읽어보니 그리디나 dp로 될거같긴 한데 생각하기 귀찮았다. N 제한이 비트마스킹으로 완전탐색 해도 될거같이 생겼다. 몇가지 구현에 헷갈리는 점이 있었지만 열심히 짜서 맞았다.

C AC (1 : 32)

 

B로 돌아왔다. 지문이 길고 문제 상황이 복잡하다. 뭘 하라는 건지 이해하는 데에만 20분은 걸린 거 같다. 특히 '현재 모닥불에서 머물거나 인접한 모닥불로 이동해 장작을 넣는다' 가 '[현재 모닥불에서 머물거나] [인접한 모닥불로 이동해 장작을 넣는다]' 인지 '[현재 모닥불에서 머물거나 인접한 모닥불로 이동해] [장작을 넣는다]' 인지 헷갈려서 운영진에게 질문을 했고, 후자라는 답변을 받았다. (이후 이 사항은 공지에도 올라왔다.) 아무튼 적당히 이해된거 같았고, 이것 역시 열심히 완탐하면 되는거 같아 열심히 짜서 제출했더니... 틀렸다! 문제를 다시 읽어보니 잘못 이해한 부분이 있어 (그런데도 채점이 60%까지나 돌았다) 수정하고, 이런저런 이슈로 몇번 틀리고 나서야 AC를 띄울 수 있었다.

B WA (2 : 01) (-1)

B WA (2 : 03) (-2)

B WA (2 : 10) (-3)

B AC (2 : 11) (+4)

 

D로 돌아와 생각을 잠시 해 보다 딱히 떠오르는게 없어서 E를 잡았다. 예제 3을 손으로 풀어보니 내가 문제를 완전 잘못 이해했다는걸 깨달았다. 어쨌든 파라메트릭이라는 큰 틀은 똑같고, 결정문제는 dp로 해결해주면 된다. $dp[i] = dp[j] + W[i]\;(j<i)$ 를 계산해야 하는데, 나이브하게 하면 $O(n^2)$ 이고, prefix max를 이용하면 선형으로 줄일 수 있다.

E AC (2 : 22, First to solve)

 

G를 열었다. G는 간선이 딱 N개니 간선 하나만 제외시켜 트리로 만든 다음, 남은 간선 하나는 잘 관리하면 되겠다는 생각이 들었다. 경로에 연산하는건 HLD로 잘 펼친 다음 쿼리는 마지막에만 날리니 누적합으로 처리하면 $O(NlgN)$에 할 수 있을거다. 근데 구현이 귀찮아보여서 일단 넘어갔다.

 

H를 열었다. 원형이니 선형 두개 이어붙여서 잘 처리하면 될거고... 쿼리 생긴게 보니 딱 봐도 레이지 같긴 한데 노드를 어떻게 정의해야 될 지 모르겠더라.

 

대회 시간은 90분 정도 남았고, E를 퍼솔하면서 단독 5솔로 1위인 상태다. 다만 나는 B C를 늦게 풀었을 뿐더러 B에서 패널티를 많이 쌓았으니, 공동 5솔일 경우 2위로 밀릴 게 뻔했다. 당시 2위는 A B C F를 풀었고, E가 크게 어렵지 않으니 곧 5솔로 올라올 것 같았다. H는 전혀 모르겠고, G는 열심히 짜면 될 거 같았고, D는 당장 생각나는건 아니지만 앞쪽에 있는걸 보면 적당히 잘 하면 될거라는 믿음을 가졌다.

따라서 한시간 정도를 G에 투자해 AC를 띄운 후, 남은 시간동안 D를 고민하기로 계획을 세웠다.

 

그리고...

-틀-

여러가지 이유로 구현 미스와 이상한 주장을 5번쯤 해서 틀리고 열심히 고쳤지만, 끝까지 AC는 띄우지 못했다. 아마 어딘가에 구현 미스가 있거나, 내가 생각하지 못한 케이스가 있을지도. 아무튼 10틀을 박고, 장렬히 전사했다.

 

마치며

G 풀이를 보니, 내가 짜려고 한 것과 방향성은 비슷하지만 몇가지 처리를 더 해서 훨씬 구현을 간단하게 만들었더라. 앞으로는 문제를 풀 때 자세한 구현 스펙과 더 간단히 하는 방법은 없는지 생각해보고 키보드 잡는 버릇을 들여야겠다.

 

대회의 퀄리티는, 내가 대회를 많이 참여해 본 적 없어서 모르겠지만, B C 둘 다 지문 개판 + 노잼 완탐이었고 전체적으로 educational한 문제가 없었던거 같아 아쉬웠다.

 

G를 풀었다면, G를 풀고 남는 시간에 D를 잡아서 풀었다면... 하는 생각이 머리에서 떠나질 않지만 그래도 2등이니 기분은 좋다. 키보드 77ㅓ억