klimmek55

AtCoder Beginner Contest 187 E. Through Path 우선 \(1\)번 쿼리와 \(2\)번 쿼리는 \(a\)와 \(b\)만 바뀐거니 \(1\)번 쿼리를 기준으로 생각할 수 있다. 일단 아무 노드나 루트 노드로 잡아서 트리를 만든다. 만약 \(a\)가 \(b\)의 자식노드라면, \(a\)의 서브트리 내의 모든 노드에 \(x\)를 더하면 된다. 만약 \(a\)가 \(b\)의 부모노드라면, \(a\)의 서브트리를 제외한 모든 노드에 \(x\)를 더하면 된다. 그리고 이 작업은 lazy propagation을 하듯이 각 노드에 자신의 서브트리에 더해야될 값을 저장해둔 뒤 모든 쿼리가 끝난 후 계산을 해주면 된다. F. Close Group 일단 \(N\)이 엄청 작다. 처음엔 \(9!..

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..

http://poj.org/problem?id=3904 $$\sum^{n-3}_{i=1}\sum^{n-2}_{j=i+1}\sum^{n-1}_{k=j+1}\sum^{n}_{l=k+1}[\gcd(a_i,a_j,a_k,a_l)=1]=\sum^{n-3}_{i=1}\sum^{n-2}_{j=i+1}\sum^{n-1}_{k=j+1}\sum^{n}_{l=k+1}\sum^{10000}_{d=1}[d|a_i][d|a_j][d|a_k][d|a_l]\mu(d)$$ $$=\sum^{10000}_{d=1}\mu(d)\sum^{n-3}_{i=1}[d|a_i]\sum^{n-2}_{j=i+1}[d|a_j]\sum^{n-1}_{k=j+1}[d|a_k]\sum^{n}_{l=k+1}[d|a_l]$$ 수 범위가 작으니 각 \(d\)마다 확인..

https://www.codechef.com/NOV15/problems/SMPLSUM 틀린 부분이 있을 것 같기도 하지만 일단 내가 이해한대로 적어본다. $$\sum ^n _{i=1}\frac{n}{\gcd (i,n)}=\sum_{k|n}\sum ^n _{i=1}[\gcd(i,n)=k]\frac{n}{k}$$ \(i=ak\)라고 하면, $$\sum_{k|n}\sum ^{\frac{n}{k}} _{a=1}[\gcd(a,\frac{n}{k})=1]\frac{n}{k}=\sum_{k|n}\sum ^{\frac{n}{k}} _{a=1}\sum _{d|\gcd(a, \frac{n}{k})} \mu(d) \frac{n}{k}=\sum_{k|n}\sum ^{\frac{n}{k}} _{a=1}\sum ^{\frac{n..

작년 KOI에서 은상을 타서 올해는 APIO를 나갈 수 있었다. 대회 일주일 정도 전부터 예전 APIO 문제들을 좀 보긴 했는데... 진짜 풀기는 커녕 부분점수도 못 받을 것 같은 문제들이 많았다. 어떤 해는 세 문제 중에 하나도 엄두가 안 나고, 어떤 해는 그래도 한 문제 정도는 풀만하기도 한걸 보면 난이도가 좀 오락가락 하나보다. 그리고 대회 때 비주얼스튜디오를 써야한다고 했는데 나는 비주얼스튜디오밖에 쓸 줄 몰라서 오히려 좋았다. 1. 이상한 기계 처음엔 보자마자 대체 뭔 소리인지 이해가 안 돼서 일단 다른 문제들부터 다 읽었다. 근데 다른 문제들이 더 멀어보여서 다시 이 문제로 돌아왔다. 일단, 주어진 구간들이 겹칠 수 있다. 그러므로 라인 스위핑을 써서 합쳐야되긴 할 것 같다. 그런데 그건 부가..

Min Max Tree 문제풀면서 이렇게 코드를 길게짜보긴 처음이다. 줄일 여지가 충분히 많긴 했지만 구현 연습하는셈치고 하나하나 다 짰다. 일단 어떤 경로 상에서 최솟값이 \(z\)라는 것은 그 경로상의 간선은 \(z\)이상이라는 의미다. 마찬가지로 최댓값이 주어지면 \(z\)이하라는 의미다. 그러면 이제 주어진 정보들을 가지고 모든 간선의 범위를 정할 수 있다. 문제는 어떤 경로 상의 구간의 최댓값과 최솟값을 업데이트해야한다는건데, 이거는 트리를 HLD로 나눈 뒤에 세그먼트 트리로 하면 된다. 그리고 모든 간선들의 범위를 정했다면, 원래 주어진 정보에 맞춰줘야 한다. 최솟값에 대한 정보였다면 그 경로에는 적어도 하나의 그 값이 있어야 한다. 이건 그리디하게? 하면 되는데, 각 정보 별로 값을 배정할 ..