전체 글 (10) 썸네일형 리스트형 LGCPC 2024 B, C 풀이 BSubtask 1 : $x = 1$구슬을 흘려보냈을 때 도착하는 위치는 왼쪽으로 이동할 때 1칸만 이동할 수 있으므로, amortized $O(1)$에 업데이트할 수 있습니다.따라서 현재 도착 위치에서 다음 도착 위치를 naive하게 구해주어도 $O(N+Q)$에 문제가 해결됩니다. Subtask 2 : $N, Q \le 5000$쿼리가 주어질 때마다 다음 배열이 어떻게 되는지 $O(N)$에 다양한 방법으로 구할 수 있습니다. 따라서 시간복잡도는 $O(NQ)$입니다. Subtask 3 : 추가 제약 조건 없음stack을 이용하여 문제를 해결합니다. 각 $A[i]$에 $i$를 더해준 후, 스택을 활용해 최댓값이 업데이트되는 부분을 저장합니다. 그 후 그 지점을 중심으로 그 지점의 원래 높이와 주변 높이가 .. 코드포스 IGM 달성 후기 2022년 11월 26일에 열린 코드포스 글로벌 라운드에서 IGM을 달성했다. 충분히 IGM을 갈만하다는 생각은 했지만 아직 레이팅이 2518이었고 2600을 찍으려면 82점이나 올려야 하기 때문에 오래 걸릴 줄 알았는데 평소보다 훨씬 좋은 성적을 거뒀고 무려 116점이 올라 레이팅이 2634가 되었다. D. Doremy's Pegging GameABC까지는 무난하게 풀었는데, D에서 처음으로 말렸다. 난이도는 플래티넘 하위 정도인 수학 문제인 것 같다. nCr 하나를 곱하면 되는데 이걸 못 보고 30분 정도 삽질했다. 충분히 빨리 풀 수 있는 문제였고, 이 문제를 빨리 풀었다면 전체적으로 점수가 높아지고 G3을 풀 시간이 생겨 티셔츠를 받을 수 있는 30등 안에 들 수 있었던 것 같아 아쉬움이 남는다... IOI 2018 5번 Highway Tolls 풀이 https://oj.uz/problem/view/IOI18_highway 문제 보기 - 통행료 (IOI18_highway) :: oj.uz 문제 보기 - 통행료 (IOI18_highway) oj.uz 모든 서브태스크에서, 도시가 모두 한산할 때의 통행료를 $w_0$이라고 한다. 이것은 1개의 쿼리를 소모해 미리 구해놓는다. 1. 5점 풀이(Subtask 1) 쿼리가 100개, 도로가 99개이므로 모든 도로에 대해 그 도로만 혼잡하게 한 다음 통행료 $w$를 계산하면 $w > w_0$인 도로들이 경로를 만들게 된다. 이 경로의 양 끝 점에 있는 두 도시가 $S$와 $T$가 된다. 2. 12점 풀이(Subtask 1, 2) 트리상에서 두 도시 $S$와 $T$의 거리는 $D = \frac{w_0}{A}$이다... 이전 1 2 3 4 다음
