-
구사과와 함께하는 PS-PT 2주차
Intro Greedy Termite (ICPC Tehran Site 2019) 다음으로 갈 위치를 빠르게 구할 수 있으면 문제를 풀 수 있습니다. 현재 $i$번째 막대기에 있다고 할 때, 다음으로 갈 막대기 $j$의 조건은 다음과 같습니다. $H_j - \vert X_i - X_j \vert$가 최대 $\vert X_i - X_j \vert$가 최소 $j$가 최소 절댓값 기호는 사회악이므로 $X_i$와 $X_j$의 대소 관계에 따라 식을 조건을 다시 정리해봅시다. $X_j < X_i$인 경우 (왼쪽으로 이동하는 경우) $H_j + X_j - X_i$가 최대 $X_i - X_j$가...
-
구사과와 함께하는 PS-PT 1주차
Intro justiceHui와 Ryute가 같이 작성했습니다. Virus Experiment (JOIOC 19 3번) Subtask 2 (6점) 적절한 전처리를 통해 $(r, c)$가 감염되기 위해서 이웃들이 감염되어야 하는 조합을 $O(16RC)$ 시간에 모두 구할 수 있습니다. (ex. 이웃이 감염된 상태가 $\left{ N, SW, WE, SE \right}$ 중 하나 이상을 포함하면 $(r, c)$도 감염됨) 위와 같은 전처리를 모두 수행했다면, $U_{r,c} \neq 0$인 모든 $(r, c)$에 대해 BFS 등을 이용해서 시뮬레이션을 하면 $O(R^2C^2)$ 시간에 문제를 풀 수 있습니다. 코드 Subtask 3 (100점) 깔끔한...
-
Linear Recurrence
이번 글에서는 선형 점화식의 $n$번째 항을 빠르게 구하는 방법에 대해 알아보도록 하겠습니다. 문제 다음과 같이 정의되는 무한수열 ${a_n}$이 있습니다. \[a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}\] $n$과 초항 $a_1, a_2, \ldots, a_k$, 계수 $c_1, c_2, \ldots, c_k$ 이 주어지면 $a_n$을 구하는 것이 목표입니다. 가장 간단한 방법부터, 이번 글의 최종 목표인 $O(k log k log n)$ 만에 구하는 방법까지 알아보도록 하겠습니다. 정의를 대입 가장 간단한 방법으로, 점화식 그대로 $a_{k+1}, a_{k+2}, \ldots,...
-
정확도 높은 FFT와 NTT
FFT에서는 실수 자료형을 사용하기 때문에 실수 오차가 발생할 수 있고, 이는 즐거운 PS생활에 큰 지장을 줄 수 있습니다. 특히 FFT 문제에서 수가 너무 크기 때문에 M으로 나눈 나머지를 출력한다.와 유사한 문장이 나온다면 실수 오차를 만나는 것을 각오해야 합니다.이 글에서는 M으로 나눈 나머지를 출력한다.같은 문장이 나오는 문제에서 약간의 속도를 희생해 FFT의 정확도를 높이는 방법과 정수만 이용해서 FFT를 하는 방법에 대해 다룹니다. ※ 이 글은 독자가 분할 정복을 이용한 FFT 알고리즘(쿨리-튜키 알고리즘)을 알고있다는 전제 하에 설명합니다.쿨리-튜키 알고리즘을...
-
2-dimension Euclidean Minimum Spanning Tree
\[\newcommand{\PhiInsert}{\Phi_{insert}} \newcommand{\PhiDelete}{\Phi_{delete}} \newcommand{\size}{\mbox{size}} \newcommand{\capa}{\mbox{capacity}} \newcommand{\di}{D_{i}} \newcommand{\dim}{D_{i-1}} \newcommand{\zig}{\mbox{Zig}} \newcommand{\zzig}{\mbox{Zig-zig}} \newcommand{\zzag}{\mbox{Zig-zag}} \newcommand{\bf}{\mbox{Before}} \newcommand{\aft}{\mbox{After}} \newcommand{\subt}{\mbox{Subtrees}}\] Intro Minimum Spanning Tree, 우리말로는 최소 신장 트리는 잊을 만 하면 등장하는 주제 중 하나입니다. 최소 신장 트리를 구하기 위해서는 보통 두 가지 알고리즘이 사용됩니다. 하나는 크루스칼 알고리즘으로 $O(E \log E)$의 복잡도를 가지고, 나머지 하나는 프림 알고리즘으로 $O(E \log V)$의 시간복잡도를 가집니다. 하지만 이 두 알고리즘 모두 한 가지 단점을 가지고 있는데, 일단 알고리즘을 수행하려면 모든 간선을 읽어야 한다는 것입니다. 이게 왜 문제인지...