나 빼고는 모두 팀 대회가 처음이라 긴장하게되서 각자의 실력보다 약간 아쉬운 퍼포먼스를 보여준 것 같지만, 크게 아쉬운 정도가 아니라 “그래도 선방했다”정도는 한 것 같아서 후회는 없는 것 같다. 다만, 풀이를 진작에 생각해냈음에도(대회 시작 3분만에) 끝까지 구현하지 못 한 문제가 있다는 점은 개인적으로 참 아쉽다.
드디어 처음으로 알고리즘 대회 본선을 위해서 서울에 올라가보게 되었다. 작년에 서울에 올라갈 기회가 2번이나 있었지만, 코로스 때문에 전부 비대면으로 시행하게 되어서 아쉬웠는데, 올해는 다행히 전부 대면으로 시행되고, UCPC에서도좋은성적을 얻어 본선에 가게 되었다.
A번 코딩은 체육과목 입니다(2min, 1 tried)
작년까지만 해도 출석체크용 문제가 없었기 때문에 뭐지? 싶어서 약간 느리게 풀었다. 풀이는 없다.
B번 N수매화검법(46min, 3 tried)
2차원 평면위에서 선을 긋는 연산을 하는데, 시작점(S)에서 끝점(E)로 긋게 된다. i번 선을을 그을 때 드는 비용은 (앞으로 더 그어야하는 선들 중 현재 긋는 선과 겹치게될 선의 개수 + 1) * w_i 가 된다. 이러한 비용을 최소화 하는 문제다.
$N$이 2,500으로 $N^2$풀이를 생각하기 위해 DP로 방향을 잡고 고민을 했다. 아무리 생각해도 DP로는 방도가 안 보여서 패스하고 다른 문제를 봤는데, 다른 문제들도 딱히 잡히는 문제가 없고, B번을 다들 풀길래 다시 봐서 해결했다.
풀이
겹쳐지는 두 선 끼리는 어떤 순서로 놓는다고해도 겹쳐지기 때문에, 두 선중 w_i가 낮은 선을 먼저 그리는 것이 이득이라는 점을 발견했고, 그러면 전체적으로 보아도 w_i가 낮은 선부터 긋는게 무조건 이득이기 때문에 w_i 순으로 정렬하고, 그냥 선분 겹쳐지는지 체크해서 전체 비용을 계산하면 되는 간단한 그리디였다.
선분 교차판별을 팀 노트에서 긁어왔는데, 2번이나 틀리게 됐다…. 알고보니 내가 다른 코드를 선분 교차판별인 줄 아는 바람에 생긴 불상사였다. 백준에서 다시 선분교차판별 코드를 긁어와서 통과를 시키긴 했는데 이거 때문에 try수 뿐만 아니라 거의 20분을 더 잡아 먹었기 때문에 너무 아쉽다.
D번 functionx(-)
f(x) = 1이 주어질 때, 두 연산에 대한 쿼리가 Q개 주어질 때 알아서 출력하는 문제다.
- f(x)에 ax + b를 곱한다.
- f(c)의 결과가 음수면 -, 양수면 +, 0이면 0을 출력한다.
보자마자 1분만에 풀이를 생각해냈는데, D번을 푼 팀이 거의 없는 상태였어서 틀린 풀이인 줄 알았는데, 맞는 풀이였다… 근데 구현이 생각보다 빡세서(좌표압축이 어려움) 3명이서 1시간을 박았음에도 불구하고 풀지 못 했다.
풀이
1번 쿼리가 들어올 때 마다 $f(x) = 0$ 에 해당하는 x를 구해서 정렬된 상태로 arr에 저장해준다. 2번 쿼리가 들어올 때 마다 c가 arr의 몇 번 째 위치인지 판별하면 정답을 구할 수 있다.
쿼리로 들어온 c의 위치가 짝수이면 음수 해를 갖고, 홀수이면 양수 해를 갖는다. 당연히 위치가 정확히 일치하면 0을 갖는다.
다만, a가 음수 일 때는 그래프의 전체 위상이 역전 되므로, a가 음수가 올 때 마다 짝, 홀을 역전 시켜서 정답을 처리해주면 된다.
이 두 쿼리를 해결하기 위해서는 insert시 O(logn)에 정렬이 되며, key가 몇 번째 인지 O(logn)에 알 수 있는 자료구조가 필요하다. segment tree의 index에 insert하면 자동 정렬되고, key 위치는 query(0, k)로 해결가능하다. 그리고 segment tree의 index에 insert하려면 당연히 정수형으로 좌표 압축이 필요하다(-b/a와 c에 대해 좌표압축).
좌표압축하는데 1시간을 박을 정도로 구현이 어려웠는데… 다시 구현해보니 왜 어려워했는지 모르겠다. 3명이 1시간씩 박았는데…..
정해도 내 풀이와 토씨 하나도 빠짐 없이 일치하기 때문에 더욱 아쉬웠다… 보자마자 풀었는데 ㅠㅠ
