역전의 제왕 (Hard) 아마 가장 간단한 방법은 PBDS(Policy-Based Data Structure)라는 라이브러리에 있는 Order Statistics Tree라는 걸 쓰는 것 같다. 이 자료구조는 정렬된 순서를 유지하면서 원소 삽입, 삭제, \(k\)번째 원소, lower bound와 그 위치를 다 \(O(\log{n})\)만에 할 수 있는 기능이 있다. 그러면 스코어보드를 구현만 하면 변하기 전 순위와 변한 후 순위를 모두 쉽게 알 수 있다. 이 것과 별개로 내가 푼 방법은 조금 다른 식이다. 우선 마지막 순위를 구하는 것은 우선순위 큐로 할 수 있다. 그런데 문제 하나를 스코어보드에 반영한 뒤에 얼마나 순위가 올랐는지는 쉽게 알 수 없다. 이 것을 구하기 위해 우선순위 큐에서 나온 참가자..
https://www.acmicpc.net/problem/10916 $$\sum^{b_1}_{x_1=a_1}\sum^{b_2}_{x_2=a_2}\cdots \sum^{b_n}_{x_n=a_n}\gcd(x_1,x_2,\cdots,x_n)$$ $$=\sum^{1,000,000}_{k=1}\sum^{b_1}_{x_1=a_1}\sum^{b_2}_{x_2=a_2}\cdots \sum^{b_n}_{x_n=a_n}[\gcd(x_1,x_2,\cdots,x_n)=k]k$$ \(x_1=kx'_1,x_2=kx'_2,\cdots ,x_n=kx'_n\)이라고 하면, $$\sum^{1,000,000}_{k=1}k\sum^{\lfloor \frac{b_1}{k}\rfloor}_{x'_1=\lceil \frac{a_1}{k}\rce..
https://www.acmicpc.net/problem/1792 $$\sum^a_{i=1}\sum^b_{j=1}[\gcd(i,j)=d]$$ \(i=\alpha d\), \(j=\beta d\)라고 하면 $$\sum^{\lfloor\frac{a}{d}\rfloor}_{\alpha=1}\sum^{\lfloor\frac{b}{d}\rfloor}_{\beta=1}[\gcd(\alpha,\beta)=1]=\sum^{\lfloor\frac{a}{d}\rfloor}_{\alpha=1}\sum^{\lfloor\frac{b}{d}\rfloor}_{\beta=1}\sum^{\min(\lfloor\frac{a}{d}\rfloor,\lfloor\frac{b}{d}\rfloor)}_{k=1}[k|\alpha][k|\beta]..
https://www.acmicpc.net/problem/11691 $$2\sum^{n-1}_{i=1}\sum^n_{j=i+1}\text{lcm}(i,j)=\sum^n_{i=1}\sum^n_{j=1}\text{lcm}(i,j)-\frac{n(n+1)}{2}$$ 이므로 \(\sum^n_{i=1}\sum^n_{j=1}\text{lcm}(i,j)\)를 구하면 된다. (코드포스 블로그 : https://codeforces.com/blog/entry/53925에 있는거랑 같은 내용) $$\sum^n_{i=1}\sum^n_{j=1}\text{lcm}(i,j)=\sum^n_{i=1}\sum^n_{j=1}\frac{ij}{\gcd(i,j)}=\sum^n_{k=1}\sum^n_{i=1}\sum^n_{j=1}[\gcd(i..
Min Max Tree 문제풀면서 이렇게 코드를 길게짜보긴 처음이다. 줄일 여지가 충분히 많긴 했지만 구현 연습하는셈치고 하나하나 다 짰다. 일단 어떤 경로 상에서 최솟값이 \(z\)라는 것은 그 경로상의 간선은 \(z\)이상이라는 의미다. 마찬가지로 최댓값이 주어지면 \(z\)이하라는 의미다. 그러면 이제 주어진 정보들을 가지고 모든 간선의 범위를 정할 수 있다. 문제는 어떤 경로 상의 구간의 최댓값과 최솟값을 업데이트해야한다는건데, 이거는 트리를 HLD로 나눈 뒤에 세그먼트 트리로 하면 된다. 그리고 모든 간선들의 범위를 정했다면, 원래 주어진 정보에 맞춰줘야 한다. 최솟값에 대한 정보였다면 그 경로에는 적어도 하나의 그 값이 있어야 한다. 이건 그리디하게? 하면 되는데, 각 정보 별로 값을 배정할 ..
단계별로 풀어보기 jh05013 Edition 문제를 단계별로 풀어볼 수 있습니다. 단계별로 풀어보기 jh05013 Edition pt.1 단계별로 풀어보기 jh05013 Edition pt.2 단계별로 풀어보기 jh05013 Edition pt.3 단계별로 풀어보기 jh05013 Edition pt.4 BOJ 길라잡이 (Beta) https://ryute.tistory.com/33 에서 보면 됩니다. BOJ 길라잡이 베타 (1) BOJ 길라잡이 베타 (2) 19-S Sogang ACM-ICPC Team Application Bronze Silver Gold Platinum 캠프 파티 Small만 풀어봤는데, 재밌고 독특한 문제들이 많습니다. 캠프 파티 (Small) 캠프 파티 (Medium) 캠프 파티..