전체 글 썸네일형 리스트형 IGM을 달성했습니다 + 잡썰 IGM을 달성했습니다. 달성한지는 한참 되었는데 블로그에는 뒤늦게 올리네요.아마 한국인중 비 IOI 국가대표, 비 ICPC WF 진출자 중에서 2600 달성한 사람은 제가 처음이 아닐까 싶네요.지금 올리는 이유? 다음 rated 대회에서 레이팅 떨어져서 강등될것 같거든요.... 2020년에 처음 레드를 찍었을때는 2600 금방 찍을줄 알았습니다. 200만 올리면 되잖아요?하지만 무려 4년이나 걸렸네요. 이마저도 판수박치기, 운적인 요소가 상당히 작용해서 달성했다는 느낌이 듭니다.다시 말해, 제가 이 자리에 있어도 되는지 의문이 듭니다. 저정도의 실력으로 감히 IGM을 자칭해도 되는걸까요? 저는 PS를 정말 오래해왔습니다. 2013년부터 했으니 11년이고, 코드포스도 10년가량 했습니다.PS를 오래 하면서.. 더보기 또 일본 여행을 다녀왔습니다(2) 2. 7월 13일 토요일 분명 9시에 모여서 오사카성으로 출발한다고 제가 여행전에 계획을 다 짜놨는데 후배놈들이 일어나지를 못해서 밍기적대다가 9시 30분에 겨우 모였습니다. 아니 어제 2차도 안간놈들이 뭘 이렇게 힘들어하는것이여아침부터 난리도 아니었습니다. 9시 8분에 일어난 사람도 있고(말했듯 9시 집합인데!!!!) 샤워실 뜨거운물 어떻게 트는지 모르겠어요 응애 하는 사람도 있었고 어우 오사카성 도착한 후에 옆에 있는 호코쿠 신사를 가봤습니다. 도요토미 히데요시상이 바로 앞에 떡하니 있더군요. 옆에서는 오미쿠지(점괘)를 팔기에 구매해봤습니다. 구매처 옆에 "무녀 아르바이트 모집중"이라고 적혀있었는데 세상에 무녀 알바하는게 애니메이션에서만 있는게 아니었군요 오따꾸의 망상이 아니었다니 세상에 진짜 놀랐.. 더보기 또 일본 여행을 다녀왔습니다(1) 후기를 쓴다는게 귀찮아서 미루고 미루다가 1달 남짓 밀려버렸네요.아무튼 7월 12~14일 일본 오사카 여행을 다녀왔습니다. 도쿄는 정말 많이 가보았는데(주로 오따꾸 성지순례하러...) 오사카는 처음 가보는것이기에 많이 설레기도 했습니다. 왜 오사카를 가느냐? 하면 크게 3가지 이유가 있는데1. 앞에서 말했듯 도쿄를 너무 많이 가봤습니다. 사실 일본은 도쿄랑 누마즈만 가봤고 오사카라는 2번째로 큰 도시조차 가본적이 없어서 색다른 곳을 가보고 싶었습니다.2. https://hyperbolic.tistory.com/11에서 적었듯 일본친구분(오사카 출신)이 한국에 왔을때 많이 놀고 마시고 그랬는데, 그때 다음에 기회가 되면 오사카 와주시죠!라고 말해서 다음 여행은 오사카가 좋겠구나 생각했습니다.3. 자랑스럽게.. 더보기 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.. 더보기 Grand Arena Party 후기 안녕하세요 하이퍼볼릭입니다. 음, 대회 후기는 정말 오랜만에 적네요. Grand Arena Party 전후로 친구 및 지인분들과 잔뜩 놀다왔기에 그에 대한 기록을 남기려고 합니다 1. Grand Arena Party 신청 및 선발 https://www.acmicpc.net/board/view/131948 에 오프라인 대회가 생긴다는 글을 보고 바로 신청했습니다. 음, 제가 나이가 나이인지라 오프라인 대회를 볼 기회가 정말 없거든요. 그래서 오프라인 대회는 기회가 되면 무조건 신청한다는 주의입니다. 오프라인 대회 참여하는 분들을 선발한다고 적혀있었지만 그 부분은 크게 걱정 안했습니다. 제가 알기로 제가 2순위로 엄청 우선순위가 높았거든요. 어쩌다 운좋게 아레나 1등한게 다행이었네요. 아무튼 그렇게 신청이 .. 더보기 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.. 더보기 이전 1 2 다음
