역전의 제왕 (Hard) 아마 가장 간단한 방법은 PBDS(Policy-Based Data Structure)라는 라이브러리에 있는 Order Statistics Tree라는 걸 쓰는 것 같다. 이 자료구조는 정렬된 순서를 유지하면서 원소 삽입, 삭제, k번째 원소, lower bound와 그 위치를 다 O(logn)만에 할 수 있는 기능이 있다. 그러면 스코어보드를 구현만 하면 변하기 전 순위와 변한 후 순위를 모두 쉽게 알 수 있다. 이 것과 별개로 내가 푼 방법은 조금 다른 식이다. 우선 마지막 순위를 구하는 것은 우선순위 큐로 할 수 있다. 그런데 문제 하나를 스코어보드에 반영한 뒤에 얼마나 순위가 올랐는지는 쉽게 알 수 없다. 이 것을 구하기 위해 우선순위 큐에서 나온 참가자..
https://www.acmicpc.net/problem/10916 b1∑x1=a1b2∑x2=a2⋯bn∑xn=angcd(x1,x2,⋯,xn) =1,000,000∑k=1b1∑x1=a1b2∑x2=a2⋯bn∑xn=an[gcd(x1,x2,⋯,xn)=k]k x1=kx′1,x2=kx′2,⋯,xn=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 a∑i=1b∑j=1[gcd(i,j)=d] i=αd, j=β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 2n−1∑i=1n∑j=i+1lcm(i,j)=n∑i=1n∑j=1lcm(i,j)−n(n+1)2 이므로 ∑ni=1∑nj=1lcm(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) 캠프 파티..