UCPC 2022에 sean9892, pentagon03 와 함께 참여했다. 3명 모두 공대 새내기라, 새내기들을 괴롭히는 과목들인 일물실, 일화실, 캘큘을 닉네임으로 하고 팀명을 '새내기 개노답 삼형제' 로 지었다. 대회 전 팀 연습은 3번정도(나는 한번 빠졌다) 설렁설렁 했고, 팀연습과 이번 예선 모두 디스코드를 이용해 각자 치뤘다. 전날 했던 SUAPC 2021 Winter 팀연습에서 나름 좋은 폼을 보여줬기 때문에, 괜찮은 결과를 기대하며 예선에 임했다. 대회 초반 ABCD(sean9892) / EFG(jjaewon9) / HIJ(pentagon03) 으로 분할해 문제를 먼저 읽었다. 역시나 A가 가장 쉬운 문제였고, sean9892가 의문의 RTE를 한번 받은 후 AC를 띄웠다. 04:19 A ..
Link https://www.acmicpc.net/problem/17635 APIO 2019 2번 Tag Union-find 오프라인 쿼리 평방 분할 Time Complexity $O(Q \times (\frac {M}{B} lgM + B^2lgB))$ $(B=BucketSize)$ 정점 $N(\leq 50,000)$개, 간선 $M(\leq 100,000)$개인 그래프가 주어진다. 1. $i$번 간선의 가중치를 $w$로 변경 2. 정점 $v$에서 가중치가 $w$ 이하인 간선들만 거쳐서 도달할 수 있는 정점의 개수를 출력 두가지 쿼리가 $Q(\leq 100,000)$개 주어진다. 오프라인으로 처리해도 된다. 1번 쿼리가 없을 때는, 간선들을 가중치의 내림차순으로 보면서 컴포넌트의 크기를 세주기만 하면 된..
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을 이용해 참가자 캠과 화면 녹화를..
Link https://www.acmicpc.net/problem/16909 Tag 스택 Time Complexity $O(N)$ 수열 $A$가 주어지고, $A$의 모든 구간 $[s,e]$의 최댓값-최솟값의 총 합을 구하는 문제다. 최댓값의 총 합과 최솟값의 총 합을 각각 구하자. 각각의 $A_i$에 대해 $A_i$보다 왼쪽에 있으면서 $A_i$보다 큰 수 중 가장 오른쪽에 있는 수의 인덱스를 $s_i$, $A_i$보다 오른쪽에 있으면서 $A_i$보다 큰 수 중 가장 왼쪽에 있는 수의 인덱스를 $e_i$이라 하자. 그러면 구간 $[a,b]$ $(s_i \le a \le i \le b \le e_i)$ 의 최댓값이 $A_i$가 된다. 그러한 구간의 개수는 $(i-s_i)(e_i-i)+e_i-s_i+1$이다..
Link https://www.acmicpc.net/problem/14870 KOI 2017 고등부 4번 Tag dp Segment Tree Time Complexity $O(N^2lgN)$ $N \times N$ 격자에 조개가 있다. 각 점에서 $(1,1)$로 최단거리로 이동하면서 조개를 주울 수 있는 최댓값을 구해야 한다. 한번만 구하는게 아니라, $N$개의 쿼리가 주어져서 한 지점의 조개 개수가 1 증가하거나 감소한다. 이때 모든 지역에서 주울 수 있는 조개 개수의 최댓값의 합을 출력해야 한다. 먼저 $(1,1)$로 이동하는것을 $(1,1)$ 에서 각 지점으로 이동하는 것으로 바꾸어 생각하자. 그러고 나면 쿼리가 없는경우 아주 간단한 dp로 풀리는 것을 알 수 있다. 이제 쿼리를 어떻게 처리하느냐가..
Link https://www.acmicpc.net/problem/16027 CEOI 2018 2번 Tag dp Segment Tree Time Complexity $O(NlgN)$ 수열과 정수 X가 주어진다. 수열의 연속된 구간의 수에 -X ~ X 만큼 더하는 연산을 단 한번 해서, 이 수열의 LIS 길이를 최대화해야한다. 구간 [l. r]에 k를 빼는게 최적이라고 하자. 그럼 구간 [1, r]에 k를 빼도 결과는 같다. 그럼 구간 [r+1, N]에 k를 더해도 결과는 같다. k가 아니라 X를 더해도 결과는 같다. 따라서 모든 i에 대해 구간 [i,N]에 X만큼 더하면서 최대를 찾으면 된다. dp1[i]: i번째 수를 마지막으로 하는 최대 LIS 길이. dp2[i]: i번째 수를 시작으로 하는 최대 L..
Link https://www.acmicpc.net/problem/17101 Tag Sparse Table Segment Tree Euler Tour Technique Time Complexity $O(NlgN)$ N개의 정점으로 이루어진 트리가 주어지고, 1부터 N까지의 k에 대해, 1번 정점부터 k번 정점까지만 사용한 트리의 센트로이드를 출력해야 한다. 정점이 하나 추가되면 센트로이드는 최대 1칸 이동한다. 그 방향은 정점이 새로 추가된 쪽일 것이다. 증명은 안해봤는데, 직관적이고 짜니까 맞더라. 1번 정점을 루트로 잡자. 새로 추가된 정점이 현재 센트로이드를 루트로 하는 서브트리 안에 있다면, 다음 센트로이드의 후보는 새로 추가된 정점에서 (거리-1) 만큼 위로 이동한 점일 것이다. 서브트리 안에 ..