전체 글 썸네일형 리스트형 일본여행을 다녀왔습니다. 일본 국경이 풀렸다고 해서 일본에 있는 PS친구들을 만나기 위해서 얼른 티켓을 끊었습니다. 이런말하기 뭐하지만, 제가 알고있는 PS러중에서 한국사람보다 일본사람이 더 많습니다(...) 제 코드포스 친구중에서도 일본인이 거의 7~80%는 되고요. 일본 PS러분들중에 특출나게 친한분들이 몇분 계시는데, 바로 러브라이브 좋아하는 분들입니다! 제가 또 엄청난 러브라이브 오타쿠기도 하고 취미가 2개나 같은(PS, 러브라이브) 사람을 만나는게 진짜 하늘의 별따기라 금방 엄청 가깝게 친해졌습니다. 그리고 그렇게 취미가 같은 분들끼리 모여서 비공식 그룹을 만들었으니 그게 바로 "러브라이브 니지가사키 스쿨 아이돌 동호회 팬클럽"입니다(...) 오따꾸 아무튼 그렇게 해서 11월 18~20일, 일본여행을 가게되었고 같은 그.. 더보기 다항식 연산들로 할 수 있는 것 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.. 더보기 UCPC 2022 출제 후기 안녕하세요, 하이퍼볼릭입니다. 블로그 자체가 처음이라 무엇을 어떻게 적어야 할지 모르겠네요. 출제 및 검수 시작으로부터 꽤 오랜 시간이 지났던지라 기억이 가물가물하지만 최대한 생각나는것을 적어봅니다. $ \ $ 1. 출제 작년까지는 석사과정이었지만, 올해부터 박사과정 학생이 되었기 때문에 저는 참가자 신분으로 UCPC를 참여하는게 불가능했습니다. 그래서 이번 UCPC 2022는 무조건 출제진을 해봐야겠다, 생각하고 여러 문제들을 고안하고 있었습니다. 지금까지 이런 대형 대회에 한번도 출제해본적 없고, 기껏해야 교내 프로그래밍 대회에 문제를 끄적이는 정도여서 제 출제 스타일을 모르시는 분들이 많을것이라 생각합니다. 저는 "지문은 굉장히 짧지만 문제는 결코 쉽지 않은" 그런 문제를 좋아합니다. 네, AtCo.. 더보기 이전 1 2 다음
