Eau de Cologne
에라토스테네스의 체에서 간단한 최적화만으로도 매우 빠르게 동작합니다. $O(N \log \log N)$ 시간복잡도를 가졌지만, 로컬에서 1억에 0.25초, 10억에 3.6초 정도에 동작합니다. HTML 삽입 미리보기할 수 없는 소스 기본적인 에라토스테네스의 체와 같은 방식으로 처리합니다. 단, 다음과 같은 최적화를 거쳐줍니다. 1번 줄: vector은 필수적입니다. 라이브러리가 bit단위로 값을 저장하기 때문에, 메모리 사용량을 획기적으로 줄일 수 있습니다. (수 800만개당 1MB입니다. 1억은 12.5MB, 10억은 125MB를 사용합니다) 2-4번 줄: 소수가 될 수 있는 수는, 3 이상의 홀수와 2 뿐입니다. 5번 줄 (i=3, i+=2): 2의 배수는 이미 불가능하다고 체크했기 때문에, 3이상의..
문제 방향과 가중치가 있는 그래프 $G = (V, E, w: E \rightarrow \mathbb{R})$가 있습니다. 여기서 사이클의 평균 가중치란 사이클을 구성하는 간선 가중치의 평균을 의미합니다. 그래프 $G$에 있는 모든 사이클 중 제일 작은 평균 가중치인 최소 사이클 평균 가중치는 무엇일까요? 엄밀히 작성하면 다음과 같습니다. 사이클이란 정점의 수열 $c = e_1, e_2, \cdots, e_k$을 의미하며, 다음 조건을 만족해야합니다. $e_i$의 끝 정점은 $e_{i+1}$의 시작 정점이어야 하며, $e_1$의 시작 정점과 $e_k$의 끝 정점은 같아야 합니다. 사이클 $c = e_1, e_2, \cdots, e_k$의 평균 가중치 $\mu(c)$는 다음과 같이 정의됩니다. $\mu_G(..
oj.uz / acmicpc.net 문제 Anna, Bruno, D-taro가 게임을 진행합니다. 게임을 시작할 때, Anna는 $1$ 이상 $2000$ 이하의 정수 $m$ 하나를 선언합니다. 이후 게임은 $Q$개의 라운드로 구성되며, 각 라운드는 다음과 같이 진행됩니다. D-taro가 Anna에게 정수 $A$를 줍니다. Anna는 $s, t$를 기계에 입력합니다. $s$와 $t$는 각 원소가 $0$ 혹은 $1$이어야 하고, 두 배열의 길이가 같아야 하며, 길이가 $1$ 이상 $m$ 이하여야 합니다. $s$와 $t$를 리플 셔플해서 얻은 배열 $u$를 Bruno에게 보냅니다. $s$와 $t$를 리플 셔플한 결과가 $u$라는 것은, $u$에 있는 수를 두 그룹으로 나눴을 때 첫째 그룹은 $s$, 둘째 그룹..
사전 지식 Lazy Segment Tree의 구현 Atcoder Library의 Lazy Segment Tree 설명: https://atcoder.github.io/ac-library/production/document_en/lazysegtree.html 레이지 세그먼트 트리는 타입 $S$와 $S \rightarrow S$로 가는 함수들의 부분집합 $F$가 존재해서, 각 원소가 $S$ 타입인 배열에서 다음 일을 할 수 있습니다. 배열의 연속된 구간과 $f \in F$가 주어지면, 연속된 구간의 각 원소를 $s_i$에서 $f(s_i)$로 바꿉니다. 배열의 연속된 구간$[s_l, \cdots, s_r]$이 주어지면, $s_l \circ \cdots \circ s_r$ 을 구합니다. 여기서 연산 $\circ..
Polynomial 관련 라이브러리입니다. Polynomial은 $\sum_{i=0}^d a_i x^i$로 표현되며, $a$에 해당하는 길이 $d+1$의 배열을 내부에 가지고 있습니다. Polynomial은 Field $F$위에서 정의되며, $\vec{a}$와 $\vec{b}$의 convolution을 계산하는 함수를 제공해야합니다. 아래에서, convolution을 계산하는 함수의 시간복잡도가 길이가 $d$인 경우 $O(d \log d)$라고 가정합니다. 생성자 인자가 없으면 빈 다항식을 생성합니다. vector를 인자로 주는 경우, $i$번째 원소를 $a_i$로 하는 다항식을 생성합니다. int deg(), void set_degree (int deg) 차수에 관한 함수입니다. $f = 0$은 차수 ..
최빈값 문제에 대한 고찰 중복을 허용하는 집합인 multiset $S$에 대해, $S$에서 $x$가 등장하는 횟수를 ${\rm freq}_S(x)$라고 씁시다. 모든 $x \in S$에 대해서, ${\rm freq}_S(x) \le {\rm freq}_S (a)$를 만족하는 경우에, $S$를 최빈값이라고 부릅니다. $S$의 최빈값은 여럿일 수는 있지만, 최빈값이 등장하는 개수인 $m$은 유일합니다. 우리는 다음 문제에 관심이 있습니다. 배열 $A$가 주어졌을 때, 배열의 $i$번째부터 $j$번째까지 원소인 $A[i:j]$의 최빈값을 효율적으로 구할 수 있을까? 이 글에서는 다음 주제에 대해서 다룹니다. 배열 $A$의 최빈값을 찾는 방법 특수한 경우를 효율적으로 해결하는 방법 ${\rm freq}_S(x)..