본문 바로가기

PS

IGM을 달성했습니다 + 잡썰 IGM을 달성했습니다. 달성한지는 한참 되었는데 블로그에는 뒤늦게 올리네요.아마 한국인중 비 IOI 국가대표, 비 ICPC WF 진출자 중에서 2600 달성한 사람은 제가 처음이 아닐까 싶네요.지금 올리는 이유? 다음 rated 대회에서 레이팅 떨어져서 강등될것 같거든요.... 2020년에 처음 레드를 찍었을때는 2600 금방 찍을줄 알았습니다. 200만 올리면 되잖아요?하지만 무려 4년이나 걸렸네요. 이마저도 판수박치기, 운적인 요소가 상당히 작용해서 달성했다는 느낌이 듭니다.다시 말해, 제가 이 자리에 있어도 되는지 의문이 듭니다. 저정도의 실력으로 감히 IGM을 자칭해도 되는걸까요? 저는 PS를 정말 오래해왔습니다. 2013년부터 했으니 11년이고, 코드포스도 10년가량 했습니다.PS를 오래 하면서.. 더보기
Power Projection Algorithm 2024-05-10) 초안 작성 수열 \(w_0, \cdots, w_{n-1}\) 및 FPS(다항식) \(f(x)\)가 주어져 있습니다. \(i=0,\cdots,m-1\)에 대하여, 다음을 전부 계산하시오:\[ \sum_{j=0}^{n-1} w_j \times [x^j]f(x)^i \] 이런게 왜 필요할까요? 어떻게 구할 수 있을까요? 1) 사전지식2) Power Projection \(\mathcal{O}(n \log^2 n + m \log m) \)3) 두 다항식 \(f,g\)의 합성 \(f(g(x))\) 계산하기 \(\mathcal{O}(n \log^2 n)\) 1) 사전지식 다음과 같은 내용들을 필요로 합니다. (1) 다항식 및 FPS에 관한 내용들(2) 다차원 FFT(3) 생성함수(4) Bost.. 더보기
Half GCD Algorithm 2023-10-05) 초안 작성 내용이 길어질것 같아 내용을 뺍니다. 1) Euclidean Algorithm과 Bezout's Identity 2) Half GCD, Full GCD 3) Half GCD, Full GCD on Polynomial 4) Half GCD Algorithm \( \mathcal{O}(n \log^2 n) \) 5) Full GCD Algorithm \( \mathcal{O}(n \log^2 n) \) 6) Inv of Polynomial(2) \( \mathcal{O}(n \log^2 n) \) 1) Euclidean Algorithm과 Bezout's Identity 두 음이 아닌 정수 \(a,b\) 가 존재한다고 가정합시다. 이 둘의 최대공약수 \( \gcd(a,b) \.. 더보기
개인용 다항식 템플릿 최근 개인 PS용 템플릿을 만들고 있는데 그중에서 다항식 관련 연산들에 관한 템플릿을 공유해보려 합니다. 최적화는 그렇게 잘되어 있지 않고, 버그가 있을 수 있습니다. 자유롭게 사용하셔도 되지만, 잘 안돌아갈수도 있습니다(...?) 지원하는 기능은 다음과 같습니다. 1. 사칙연산: 다항식간의 +,-,*,/ 연산을 지원합니다. 나눗셈은 일반적으로 잘 정의가 안되니 다항식 환(혹은 formal power series)이여야만 정의가 된다는것을 유의해주세요. 자세한것은 제 이전 다항식에 관한 글 참고해주세요. 2. exp, log, pow를 지원합니다. 역시 다항식 환위에서만 정의됩니다. 3. 미분,적분인 derivative, intergral을 지원합니다. 4. 다항식 값을 판단하는 eval 함수를 지원합니.. 더보기
롤링 해시를 할때 주의해야 할점 해싱을 해야하는 문제에서 계속 터져서 하도 화가 난 나머지 오랜만에 블로그 글을 적습니다. 지금까지 제가 당해보며 얻게 된 해싱 관련 팁을 공유합니다. 만약 다른 해싱 관련 팁이 있으면 제보해주세요. 1. 해싱이란 문자열 $a[1,2,...,n]$이 존재하고, 어떤 적절한 숫자 $x$와 $p$가 존재할때, 다음과 같은 값을 정의할 수 있습니다. $f(a,x,p) = a[1] x^{n-1} + a[2] x^{n-2} + \cdots + a[n] x^0$ mod $p$ 이렇게 어떠한 문자열$a$를 한개의 값 $f$로 표현하는것을 해싱이라고 합니다. 사실, 해싱 방법은 위에서 적힌 수식 말고도 여러가지가 존재하나 PS에서 해싱이라고 하면 십중팔구 저 위에서 적힌 해싱방법을 이용합니다. 위 방법은 롤링 해시(R.. 더보기
다항식 연산들로 할 수 있는 것 2022-10-15) 미완성이지만 일단 초안을 업로드했습니다. 계속 내용 수정중에 있습니다. 2022-11-16) 부족한 부분들을 많이 채워넣었습니다. Shift of Sampling Points of Polynomial이외의 모든 내용을 넣었으며, 추후 다른 토픽들을 더 추가할 예정입니다. 또한 각 토픽에 대한 연습문제 링크를 첨부하려고 합니다. 이전 글이 너무 길어질것 같아서 다항식 연산의 응용문제들을 따로 뺐습니다. 이 글에서는 다음 문제들을 다룰것입니다. 0. 목차 1. Polynomial Taylor Shift $ \mathcal{O}(T \log T) $ 2. #p Subset Sum $ \mathcal{O}(T \log T) $ 3. Partition Number 계산 $ \mathcal{O.. 더보기
어려운 다항식 연산들에 대하여 2022.10.08) 현재 내용 수정, 추가중에 있습니다. 2023.10.05) 두 다항식의 gcd에 대한 내용을 추가했습니다. 요즘 PS판이 고여가면서(?) 옛날에는 엄청 어려웠던 알고리즘들이 요즘은 기본지식이 되어가는 경우가 종종 있습니다. 가장 대표적인 어려운 알고리즘중 하나가 FFT로, 예전에는 정말 아는 사람들만 아는 어려운 지식이었지만 최근에는 PS 하는 고인물들 사이에서는 기본지식처럼 되버린 알고리즘입니다. FFT에 관한 구체적인 지식은 건너뛰고 결과만 간략하게 말하면, "두 다항식을 빠르게 곱하는 방법"입니다. 하지만, "두 다항식을 곱하기"는 "여러 다항식 연산들" 중에서는 가장 쉽고, 직관적인 연산중 하나입니다(FFT가 쉽다는게 아닙니다! FFT는 충분히 아주아주 어려운 알고리즘입니다).. 더보기
ACL에서 1줄만 추가해서 Segment Tree Beats 구현하기 2022-08-13) 초안을 작성했습니다. 일단 글을 완성하는 것을 목적으로 하였기에 부족한 부분이 매우 많이 보입니다. 부족한 예시를 채워 넣고 가독성을 높일 방법을 찾아야겠습니다. 부족하거나 어설픈 내용 수정은 이 작업이 끝난 뒤에 해야겠네요. 2022-11-10) 내용을 보강하였고, 오타를 수정하였습니다. 치명적인 오류가 있지 않는 한 더 이상의 수정 예정은 없습니다. 이 글은 Segment Tree, Lazy Propagation, Beats에 관하여 이미 지식이 있는 분들을 대상으로 하는 글입니다. 따라서 처음 Segment Tree Beats를 배우시려는 분들이 읽기에는 어려울 수 있습니다. 또한 ACL의 사용법을 이 글에서 따로 설명하지 않으니 유의 바랍니다. 0.목차 1. Group/Mon.. 더보기

티스토리툴바