7/21 금요일날 UCPC 대비로 SWERC 2020-2021 셋을 1컴으로 돌았다.
팀원은 leinad2(최다니엘), sciencepark(박민철)이다.
링크 : https://codeforces.com/gym/103081
Dashboard - 2020-2021 ICPC Southwestern European Regional Contest (SWERC 2020) - Codeforces
codeforces.com
총 13문제였고, A는 쉬운 문제일 확률이 높다는 이론에 따라 5문제/4문제/4문제로 나누어 다니엘이 ABCDE, 내가 FGHI, 민철이가 JKLM을 잡았다.
A(18분 솔브) : 다니엘이 잡고 풀었다. 난 문제도 모른다.
E(21분 솔브) : 다니엘이 A를 푸는 동안 스코어보드를 보니 E가 많이 풀리고 있어서 문제를 넘겨받고, 대신 수학이 많이 필요할 거 같은 F를 수학을 잘하는 다니엘한테 넘겼다. 봤더니 정말 쉬운 문제였다. 입력 받은 a b에 대하여 b/a의 minimum을 구하여 출력하면 된다. 다니엘이 A를 제출한 후 바로 컴퓨터를 넘겨받아서 코딩 후 AC를 받았다.
F(34분 솔브) : 다니엘이 넘겨받은 F를 코딩해서 풀었다. 완전 수학 문제는 아니고 트리에서 경우의 수를 잘 따지는 조합론적 dp문제이다.
C(51분 솔브) : 내가 맡은 FGHI는 다 읽어본 상황이었고, 다니엘이 F를 코딩하는 동안 스코어보드에 약간의 솔브가 있는 C를 읽어봤더니 풀이가 보였다. 민철이가 K를 코딩했지만 TLE가 나온 이후 컴퓨터를 넘겨받아 풀었다.
풀이는 이분탐색이다. x 이상의 거리를 무조건 유지하면서 (0,0)에서 (X,Y)로 이동하는 문제는, 각각의 점을 중심으로 반지름이 x인 원을 그린 다음 그 원을 지나지 않으면서 잘 이동하는 문제와 같다. 그런데, 만약 어떤 두 원이 만나지 않는다면 우리는 그 두 원 사이를 어떻게든 잘 지나갈 수 있다. 만약 두 원이 만난다면 두 원 사이를 지나가는 것은 힘들고 더 바깥으로 둘러가야 할 것이다.
그래서 (0,0)에서 (X,Y)로 이동을 하지 못하게 되는 경우를 그려보면 대충 이런 느낌이다.
이 그림을 보면 대충 그래프가 하나 모델링된다. 원 하나하나를 정점으로, 그리고 직사각형의 변 네 개를 정점으로 잡는다. 그리고 원과 원이, 원과 변이 닿는다면 그 사이에 간선을 추가한다. 이때 어떤 변에서 어떤 변이 같은 컴포넌트에 속하고, 그게 (0,0)에서 (X,Y)로 향하는 길을 막는 형태라면 이동이 불가능하다. 이는 dfs로 O(N^2) 또는 union find로 O(N^2logN)에 짤 수 있고 여기에 답의 필요한 정확도에 비례하는 이분탐색의 시간복잡도를 곱하면 된다. union find의 상수가 작아서 나는 union find로 코딩했다.
D(58분 솔브) : 쉬운 문제였고, 내가 C를 짜는동안 다니엘이 풀이를 내고 내가 맞은 이후 코딩하여 맞았다.
K(81분 솔브) : TLE를 내고 또 한참 고민하던 민철이가 결국 K를 고쳐서 맞았다.
I(87분 솔브) : 다들 컴퓨터를 사용하여 코딩하는 동안 나는 내가 맡은 문제들을 고민했고, 그 중 I가 제일 할만해보여 I를 잡았다. 문제를 잘 환원시켜보면 문제의 기본은 그래프의 지름(두 점 사이의 최단경로 중 가장 긴 것으로 정의)을 두 배 범위에서 estimate하는 것이었다. (실제로는 지름의 로그를 1 범위에서 estimate하는 문제이다.) 그러면 풀이는 간단하다. 일단 지름을 잡는다. 그리고 그래프의 아무 점을 잡는다. 그리고 지름 위의 아무 점으로 향하는 최단경로를 그린다. 그 도중에 다른 지름 위의 점을 만난다면 그 점에서 멈춘다. 그런 후, 지름의 양끝점 중 더 먼 곳으로 지름을 따라 이동한다. 그럼 경로의 최종 길이는 적어도 지름의 절반을 넘기 때문에, 두 배 범위의 estimate가 가능하다. 이 알고리즘의 진정한 의미는, 임의의 점 u를 잡아도, 최단경로의 길이가 지름의 절반이 넘는 어떤 점 v가 존재한다는 것이다. 그러므로 아무 점이나 잡고 가장 먼 최단경로를 가지는 점을 찾으면 된다.
H(116분 솔브) : 다들 풀 문제를 꽤 마무리한 7솔 상황. 괴악해보이는 G는 다니엘한테 넘기고 나는 H를 잡았다. 별로 어려운 문제는 아니라는 확신은 있었고, 실제로 그렇게 어려운 문제가 아니었다. 결국 어떤 수는 set에 한 번 insert됐다가 delete된다. set의 크기에 1을 더하다가 다시 안 더하게 되는 그런 상황으로 볼 수 있다. 이 상황에서 우리는 어떤 시점 t에 x 이상의 수가 몇 개 있었는지만 t가 불규칙적으로 주어지는 online 쿼리로 처리해줄 수 있으면 되는데, 간단하다. 만약 set의 크기를 다 관리하고 있다면 문제는 쉬울 것이다. 하지만 x 이상인 수에 대한 set의 크기를 모든 x에 대해 다 관리하려면 메모리와 시간이 부족하다. 그러므로 세그먼트 트리의 아이디어를 이용하여, 구간마다 l~r 사이의 수들에 대한 set 크기를 저장한다. 이때 N개를 저장하면 메모리가 부족하게 되지만 l~r 사이의 수가 들어오고 나가는 시점들만 저장하면 O(r-l+1)에 저장할 수 있다. 결국 시점 t에 x 이상의 수가 몇 개 있었는지는 x~N-1 구간을 세그먼트트리의 O(logN)개의 구간으로 다르게 해석한 다음 거기서 시점 t에 셋의 크기가 얼마인지를 다 구해서 더해주면 된다. typical한 자료구조 문제였고, 코딩해서 AC를 쉽게 받았다.
G(170분 솔브) :
문제 조건이다. 보시다시피 매우 기괴하다. 그래도 결국 환원해보면 순열사이클을 다루는 문제로 바꿀 수 있고, 다니엘이 결국 AC를 받았다.
L(200분 솔브) : L은 스코어보드 상에서 굉장히 많이 풀린 문제였고, 우리도 L을 풀어야 한다는 압박감을 많이 받고 있었다. 하지만 영어 해석 이슈도 있었고(아직도 지문을 완전히 이해하진 못했다) 그래서 잘 풀리지 않고 있었다. 나는 L을 푸는 것이 다른 남은 세 문제에 박치기하는 것보다 월등히 기댓값이 높다고 판단하고 팀원들이랑 함께 모두 L을 고민했다. 그리고 내가 그럴듯한 알고리즘을 찾았다. 하지만 지문도 완전히 이해하지 못했다는 사실에서 알 수 있듯이 그냥 그럴듯할 뿐이지 맞다는 확신을 전혀 할 수 없었다. 하지만 이런 풀이로 풀리는 것이 아니라면 이렇게 많이 풀리지 않을 것 같다는 생각에 구현했고, 놀랍게도 맞았다. 풀이는 꽤 단순한 편인데, 손님마다 먼저 1순위 레스토랑에 배치해주고, 레스토랑에서는 정원을 초과하는 손님을 '추방'한다. '추방'된 손님은 그 다음 순위의 레스토랑을 찾아가고, 레스토랑은 자리가 있다면 손님을 받아주고 자리가 없다면 그 손님의 우선순위에 따라 받아주지 않거나 그 손님을 받아주고 최하 우선순위를 가진 손님을 '추방'한다. 매 과정마다 한 손님이 현재 보고있는 레스토랑의 우선순위가 1씩 증가하므로 결국 100만logN(logN은 손님들의 우선순위를 레스토랑에서 관리하기 위한 우선순위큐의 시간복잡도)에 문제를 풀 수 있다.
이후 남은 문제가 BJM이었는데, 세 문제를 모두 읽어본 결과 가장 풀만한 문제는 J였다. J에서도 꽤 풀이에 진전이 있었다. 카드를 쌓거나/맨윗장을 뺀다 대신에 쌓고 맨윗장을 빼는 과정을 한 세트로 묶어버린 간선들을 잘 생성한 다음 쌓거나/세트로 묶인 간선을 타고가며 변화는 없다 이런 식으로 다르게 바꾸었고 실제 풀이에서도 이런 형식을 사용하였다. 하지만 여기서 조금 더 주의해야 할 점을 생각하지 못해서 AC를 받지 못했다.