$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

ICPC Preliminary 2020::::Gratus' Blog

ICPC Preliminary 2020

알고리즘 문제풀이/대회 후기, 문제풀이 2020. 10. 11. 11:49

새 팀인 Swift Turtwig로 2020 ICPC 인터넷 예선에 참가했다. 이번에 워낙 진출티켓이 적고 서울대 팀들이 터무니없이 잘하기 때문에 진출은 어려웠지만, 나름 재밌게 공부하면서 할 수 있었다. 작년 팀이랑은 또 다른 느낌인 듯.


Phase -1. Preperation

팀연습은 두번 했다. NCPC 2018이랑 NWERC 2015를 돌았고, NWERC는 아직 블로그 후기는 다 쓰지 않았는데 (문제수가 많다..ㅋㅋ) NWERC 연습은 굉장히 잘 돌았다. 3시간 셋이면 골드 3-4문제와 플레 하나, 잘하면 두개 정도까지는 쳐낼 수 있을 것 같아 보였다. 

팀노트는 kactl repository에 기반하여, 작년보다 훨씬 extensive하게 작성했다. geometry 같은 라이브러리가 없어서 실패하는 일이 없어야 한다고 생각하기도 했고, 나는 개인적으로 작년에 Dynamic CHT가 없어서 문제를 못 푼 기억이 그대로 남아있기 때문에... 결과적으로는 쓸일이 많지 않았지만.


Phase 0. Contest begins

사상 초유의 비대면 ICPC이기 때문에, zoom을 기기 2개에다가 세팅해야 하는 등 굉장히 복잡한 사전 준비 과정이 있었다. 문제지 인쇄를 각 팀이 개별적으로 해야 하기 때문에 프린터도 준비해야 하고...

이 모든 사항들을 준비하고 2시 10분에 대회가 시작했다. 문제지 합본을 못 찾고 개별 문제를 프린트하느라 초반에 프린트하는데 굉장히 많은 시간이 들었다.


Phase 1. Easy problems (I, E)

스코어보드를 보고 가장 쉬운 두 문제를 찾아서 그냥 내가 밀었다.

 

I. Project Teams

난이도 : Solved AC Silver 4

$2n$ 개의 수를 $n$개의 그룹으로 2개씩 나누어 넣는데, 각 그룹의 합의 최소값을 최대화하는 문제.

정렬해서 앞뒤에서 하나씩 뽑는게 최선의 전략임이 알려져 있다.

 

E. Cycle Game

난이도 : 예상 Gold 4

평면 상에서 뭔가 하는거라 선분 교차를 판정하는 기하문제인줄 알았는데, 그냥 간선들이 주어지고 언제 처음 사이클이 생기는지 판단하는 문제였다. 정확히 이 일을 수행하는 Union find 라는 자료구조가 있다. (Disjoint set 이라고도 한다)

백준 기준 1717 (집합의 표현) 이 골드 4이므로 이것도 그쯤 될 듯.


Phase 2. Mild struggles (K, L)

그다음으로 많이 풀린 문제인 K, L을 잡았는데, 둘다 약간씩 문제가 있었다. 

 

L. Sliding coins

난이도 : Solved AC Gold 2

o와 x로 구성된 10,000자리 문자열 S, T가 주어지고, S의 인덱스 두개가 주어진다. 이때 주어진 인덱스의 글자들을 '움직일' 수 있는데, 아무렇게나 움직여도 좋지만 이 두개의 relative order는 유지되어야 한다. 이때 S에서 이 두 글자만 움직여서 T를 만들 수 있는지의 문제.

S에서 움직일 수 있는 두 개를 미리 빼 놓고, $n-2$ 개와 $n$ 개짜리 문자열들의 Longest common subsequence를 구한 다음, 남은 두개의 relative order를 보는 Naive 풀이가 있지만, LCS 한번에 $O(n^2)$ 인데다가 LCS 여러 개 중 relative order 성질을 만족하는것 하나를 찾기가 어려워서 이 풀이는 불가능하다.

처음에는 Greedy하게 S와 T의 글자들을 왼쪽부터 보면서 안되면 아까 빼놓은 글자들을 쓴다고 생각했고, 나는 이 풀이가 맞다고 잠시 확신을 가졌지만(...) 코딩하던 sprout이 계속 '아 이거 아닌 거 같은데' 하는 식으로 얘기했다. 그래도 일단 코딩을 해서 Wrong answer를 받고, 다시 생각해보니, 글자가 맞더라도 빼놓은 글자를 써야 하는 경우가 있을 수 있어서 그리디하게 해결할 수 없다.

문제를 다시 보고 나랑 sprout이 같이 3N dp를 생각해서 다시 코딩해서 맞췄다. 대략 $D_{i, j}$ 를, $i$ 번까지 $j$개의 '스킵' 을 쓰면서 (스킵은 앞서 빼 놓은 2개를 말한다) 진행할 수 있는지로 정의하면, $D_{i-1, j-1}$ 과 $D_{i-1, j-1}$만 보면 할 수 있다.

 

K. Road reconstruction

난이도 : Solved AC Gold 4

이번 대회에서 우리 팀 최고의 병크.

간단히 말하자면, 각 칸을 지나는 데 INF / 0 / 1 / 2 의 비용이 드는 칸들이 있을 때, $(1, 1)$ 에서 $(n, m)$ 으로 가는 최단 경로의 길이를 찾는 문제이다. 이는 각 정점이 가중치를 갖는 최단 경로 문제로 생각할 수 있다. 

그래프를 잘 모델링하면 최단 경로를 찾는 것은 어렵지 않은데, 첫번째로 생각한 모델링이 무려 각 칸마다 상하좌우로 이동하기 위한 4개의 정점을 추가로 만들고, 이들을 complete graph처럼 이어놓고 PPAP를 추는 이상한 모델링으로 3명이 순간 다같이 뇌절해서 이런 기괴한 모델링에 동의했다. 그런데 이런식으로 모델링을 하면 $n, m$ 이 1000정도 될때 수백만 개의 정점과 천만개 이상의 간선을 쓰게 되는데, 간선이 1e7개인 다익스트라 알고리즘을 1초 안에 집어넣을 자신이 별로 없었다.

모델링을 수정했어야 하지만 이때 내가 "아 ㅋㅋ 간선이 0 1 2밖에 없으니까 0-1 BFS를 확장해서 0-1-2 BFS처럼 쓰면 $O(3E)$ 에 풀 수 있음 ㅋㅋ" 이런식으로 말하고 구현을 시작했고, 팀원들이 다들 와 그러면 되겠네~ 하는 식으로 반응했기 떄문에 (...) 구현에 들어가서 기괴한 모델링에 고통받았다. 한참 뒤에 팀원들이 F를 생각하는 동안 내가 구현을 잡으면서 제대로 된 모델링을 떠올려서 모델링부터 다시 코딩헀다.

제대로 된 모델링은, 각 정점을 in 정점과 out 정점으로 분할한 다음, 들어오는 모든 간선을 in에, 나가는 간선을 out에 배정하고, in-out 간선을 정점 가중치만큼 가중치를 주는 것이다. 이렇게 하면 정점이 200만개, 간선도 몇 백만 개 정도에 불과하므로, 다익스트라 알고리즘을 이용해서 넉넉히 통과할 수 있다.

그러나 아까 이상한 모델링에다 대고 BFS를 다 짰기 때문에, 어쩌다 보니 그냥 0-1 BFS 기반의 코드를 그대로 짜서 맞았다. :( 

이때 시간을 낭비하지 않았으면 D를 풀 수 있었을 것 같아 특히 아쉽다.


Phase 3. Spurt

 

F. Escaping

매우 허무한 문제.

평면에 경찰이 $N$명 깔려 있고, 도둑이 한명 있다. 이 도둑이 밖으로 도망치려고 하는데, 모든 사람이 한번에 한 칸씩 (도둑이 먼저) 움직인다고 할 때, 도둑이 모든 경찰을 피해 도망칠 수 있는지 판정하는 문제.

문제를 딱 읽고 내가 "와 이거 근데 막 그냥 한줄로 쭉 도망쳐서 되는지 아닌지 보는거면 웃기겠다" 라는 식으로 던지고 K를 구현하러 갔는데, heatz와 sprout이 그동안 생각을 하더니 "반례를 모르겠다. 그냥 그렇게 하면 맞을거 같다" 라는 식으로 얘기가 나왔다. 구현하면서 살짝 어이가 없었지만 사실 나도 별로 뾰족한 수가 없었기 때문에 그대로 짜보기로 하고 K번 구현한 다음 컴퓨터를 sprout에게 넘겼는데, AC를 받아왔다. 

끝나고 작년 팀원들에게 물어보니 Coffeetea가 비슷하게 발상을 던지고 Diordhd가 어느정도 증명을 했다고 한다. Coffeetea가 평소에 이런 스타일의 뜬금없는 발상에 매우 강하지만 Diordhd가 그걸 바로 믿지 않고 증명해보는 일은 작년 우리팀에서 매우 많았다. (Coffeetea의 발상이 맞음을 확인할 때와 Diordhd가 반례를 찾아내는 경우가 둘다 적지 않아서 나는 보통 그동안 그걸 코딩하고 있었긴 하다. ㅋㅋ)

 

H. Negative Cycle

문제 제목만 보고 벨만포드로 음수사이클 찾는 문제를 생각했는데 아무 관련 없다.

대충 +1과 -1 가중치를 갖는 그래프가 주어지고, 가중치의 곱이 음수인 사이클을 찾는 문제이다. 이 문제는 +1을 0으로, -1을 1로 놓고 나면, 가중치가 홀수인 사이클을 찾는 문제가 된다.

나랑 sprout이 똑같은 풀이를 각각 생각했는데, 대충 다음과 같다. 

정점을 dfs 순서로 돌면서 정점에 검정색과 하얀색을 칠한다. 루트를 검정색으로 놓고, 0 가중치로 잇는 경우는 그대로, 1 가중치로 잇는 경우는 색깔을 바꾸면서 DFS를 돌린다. 이때, DFS 를 도는데 사용하지 않았던 간선 e에 대해서, e가 색깔이 다른 점 (u, v)를 잇는 0 간선이거나 색깔이 같은 점 (u, v)를 잇는 1 간선인 경우, 다음이 홀수 사이클이 된다.

e + path(lca(u, v) to u on dfs tree) + path(lca(u, v) to v on dfs tree).

첫번째 케이스의 경우, lca(u, v)가 어느쪽 색이든, 두 path 중 하나의 가중치는 홀수이고 하나는 짝수이다. 거기에 0 간선을 추가한 것이므로 홀수 사이클이 된다. 두번째의 경우, lca의 색과 무관하게 두 path의 가중치의 합은 짝수이다 (각각이 홀수인지 짝수인지는 알 수 없으며 중요하지 않다). 따라서, e가 1 간선이 경우 홀수 사이클이 된다.

 

내 풀이의 경우 여기에서 차이는, 한 정점에서 BFS를 돌면서 각 정점까지의 path의 가중치 합을 계산해놓고 그걸 기준으로 한다는 점인데, 사실 이 가중치 합의 홀짝성이 위 풀이에서의 색깔과 같고, 위 방법이 구현이 훨씬 간단했을 것 같다. 내가 조금 먼저 생각해서 컴퓨터를 잡았기 때문에 오히려 더 늦어진 것 같기도...


Phase 4. Last 20 minutes

마지막 20분 동안 D를 생각했고, 4*n칸의 DP를 $n^2$ 시간에 갱신하는 느린 솔루션을 찾은 다음, 이를 세그먼트 트리 4개를 만들어 $n \log n$으로 줄이는 방법을 떠올렸으나 시간이 촉박해서 코딩을 완성하지 못햇다. 한 10분 정도만 더 있었으면 해볼만 했던거 같은데 이런저런 이유로 시간이 부족했던 것 같아 아쉬움이 많이 남는다. 3명 1PC 3시간 대회는 솔직히 시간이 터무니없이 짧다 ㅜㅜ


Results & Thoughts

스코어보드가 아직 공개되지 않았지만 프리즈 이전 기준으로 30등 정도였고, 그후 우리가 H번을 풀긴 했으나 한문제를 푼 팀은 상당히 많을 것이므로 등수가 많이 올라가지 않을 것이다. 그러나 두문제를 풀기에도 촉박한 시간이기 때문에 딱히 많이 떨어질 것 같지도 않다. 대략 30등 근처라고 생각할 수 있을 듯.

서울대학교 팀들이 프리즈 전 기준으로 놀라운 성적을 거뒀다. 1-5등을 모두 챙겨갔고, 7등도 서울대 팀으로 10등 이내에 서울대 6팀, KAIST 4팀으로 끝났던 것으로 기억한다. 올해의 경우 리저널 진출팀이 60팀으로 크게 줄어들었고, 지난 몇년의 전례로 보아 특정 대학의 팀이 많이 진출하는 일을 막고 다양한 대학의 참가를 지향하는 ICPC 측의 리저널 진출팀 선정 방식에 비추어 볼 때 올해 서울대의 티켓은 4-5장일 것이라는 추측이 있었는데, 이런 경우는 어떻게 될지 사실 살짝 궁금하다. 10등권 초반에서도 예선에 탈락하는 초유의 사태가 벌어질지도 모른다.

만약 그렇다면 내년 ICPC도 과연 본선에나 갈 수 있을지...

 

나름 PS 공부한다고 (대학 와서 시작한거지만) 하면서도 정작 ICPC 한국 리저널 무대를 한번도 못 밟아 본 건 좀 많이 아쉽다. 내년에 다시 90팀으로 늘려준다고 해도 현황을 봤을 때 서울대에서 ICPC 본선 진출하려면 10등 내외여야 안정적으로 진출할 수 있는 것 같고, 그러려면 적어도 코포 레드 내지는 근접한 실력의 팀원 3명이 호흡을 잘 맞춰야 가능할 것이다. 만약 그렇다면 본선 수상보다 본선 진출이 더 어려운 기이한 예선이 되는 것인데, 뭐 대회 룰이 그렇다면 뾰족한 방도는 없다만, 또 마음은 그게 아니니까.

 

여튼 비대면 대회임에도 상당히 재밌게 치를 수 있었다. 멋진 팀원들 덕분이라고 생각하기로 했다. ㅋㅋ

아직 갈길이 멀다.

 

admin